C Doubly Linked Lists

Page 1 of 2

Author: Brian Moriya Published on: 26th Jun 2011

In this tutorial you will learn about C Programming - What is Doubly linked lists, Adding Nodes Doubly linked lists, Traversing a Doubly linked lists and working with Doubly linked list Example.

Doubly linked lists are the same as singly linked lists, except they have an extra pointer per node so they point to the next node and the previous node. You just make sure that whenever you insert a node you set next to the next node and previous to the previous node. They will also commonly keep a tail and head pointer so that traversal may start at either end of the list.

Doubly Linked List Nodes

A doubly linked list node would look like this:

Sample Code

struct dllnode {
Arbitrary Data Portion
struct dllnode *next;
struct dllnode *previous;
};

Ads

It contains a data portion and a pointer to both the next and previous nodes in the list sequence allowing for two-way traversal.

Creating A Doubly Linked List

When creating a doubly linked list, we want to be able to go both ways as well as be able to start at either end of the list when traversing it. As mentioned earlier, we use a both a tail and a head pointer to provide this functionality.

Checking for head being NULL is sufficient for checking for an empty list.

Sample Code

if (head == NULL) {
//This node becomes the first and last node in the list.
newnode->previous = NULL;
newnode->next = NULL;
head = newnode;
tail = head;
}

Pretty much the same as we have done throughout this tutorial with the singularly linked lists, with the addition of the previous pointer needing to be set to NULL and the tail also being equal to the new node.

Inserting Nodes

Same as linear singularly linked lists, we can add at the beginning, middle, or end of a doubly linked list.

Placing a node at the beginning of a doubly linked list is quite simple but an empty and nonempty must be handled differently.

When the list is empty all you have to do is create the new node, set its next and previous pointers to NULL, and point the head and tail pointers to it. We already saw the code for this in the last section.

Inserting a new node at the beginning of a nonempty doubly linked list is a little tricky, but not impossible. First you create your new node and set its previous pointer to NULL, but the next pointer to the current head. Then set the current head's previous pointer to the new node being inserted to move the old head one up in the list. Now all you have to do is point head at the new node and you are done.

In code it should look something like this

Sample Code

newnode->previous = NULL;
newnode->next = head;
head->previous = newnode;
head = newnode;

Insertion of a new node at the end of the list is quite similar although we use the tail pointer as a reference instead of the head pointer. Since the empty list case here is identical to the empty list case above for insert at beginning we will skip it.

To place a node at the end of the nonempty list you create the new node, set its next pointer to NULL and its previous pointer to the current tail. Then set the current tail's next pointer to the new node. Now point tail to the new node which you have inserted a node at the back of the list. Although it's not in our example, here is a code snippet

Sample Code

newnode->next = NULL;
newnode->previous = tail;
tail->next = newnode;
tail = newnode;

Note the similarity to the sample for insertion at the beginning.

Here's the fun part, this is the greatest feature of the doubly linked list. It's actually so simple though, you may be disappointed.

Forward traversal is identical to singly linked list traversal. Seriously, there is no difference. This should look familiar.

Ads

Sample Code