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:
struct dllnode {
Arbitrary Data Portion
struct dllnode *next;
struct dllnode *previous;
};
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.
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
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
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.
if (head != NULL) {
currentnode = head;
while (currentnode->next != NULL) {
currentnode = currentnode->next;
}}
With that in mind, you would think that going the other way would be the same but with the tail pointer. You would be correct.
if (tail != NULL) {
currentnode = tail;
while (currentnode->previous != NULL) {
currentnode = currentnode->previous;
}}
A common thing to do in game programming is to keep a list of objects currently on the screen. One reason is for updating the screen to make them appear to move. Linked lists are perfectly suited to this purpose because of their dynamic nature. Let’s make a list of the x and y coordinates of all objects currently displayed on a screen for an arbitrary game.
The sample has one function for adding nodes to the front of the list. It takes into account the empty and nonempty list cases we learned about above.
Then it creates five objects that have an x and y coordinate, and adds the nodes to the list by calling the addnode function and passing it the newly created node, thus making the last node added at the beginning of the list and the first node added the end.
After the list is created and all the game objects coordinates are known, we traverse the list from the beginning to the end and print all the x and y values for each object. Then we do the same, but start from the tail and go back to the head.
#include <stdio.h>#include <stdlib.h>struct dllnode {
int x;
int y;
struct dllnode *next;
struct dllnode *previous;
};
//Here's the doubly linked list root pointers.struct dllnode *head = NULL;
struct dllnode *tail = NULL;
void addnode(struct dllnode *newnode) {
if (head == NULL) {
//This node becomes the first and last node in the list.newnode->previous = NULL;
newnode->next = NULL;
head = newnode;
tail = head;
} else {
//List is not empty, insert at front of list.newnode->previous = NULL;
newnode->next = head;
head->previous = newnode;
head = newnode;
}}void main() {
int i;
int x, y;
struct dllnode *current;
//Create 5 objects in a diagonal line across the screen from eachother.for (i = 0; i < 5; i++) {
struct dllnode *newnode;
x = y = i;
newnode = (struct dllnode *)malloc(sizeof(struct dllnode));
newnode->x = x;
newnode->y = y;
addnode(newnode);
}//Traverse the list and print the current position of each object.current = head;
i = 1;
while (current != NULL) {
printf("Object %d: ", i);
printf("n");
printf(" x position: %d", current->x);
printf("n");
printf(" y position: %d", current->y);
printf("n");
i++;current = current->next;
}//Do the same but start at the back of the list.current = tail;
i = 1;
while (current != NULL) {
printf("Object %d: ", i);
printf("n");
printf(" x position: %d", current->x);
printf("n");
printf(" y position: %d", current->y);
printf("n");
i++;current = current->previous;
}}
