# Doubly Linked List Tutorial

Continuing with our tutorials series on data structure, let’s discuss Doubly Linked List in this article. Earlier in this series of article we discussed Singly Linked List, it’s definition and various operations which can be performed on it along with code snippets. Let’s now dig into Doubly Linked List and understand what all operations are supported by it.

[linkad]

**Definition:**

A doubly linked list, in computer science, is a linked data structure that consists of a set of sequentially linked records called ** nodes**. Each node contains two fields, called

*links*, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’

**previous**and

**next**links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

Noticeable differences between singly and doubly linked lists :

- Although doubly linked lists require more space per node as compared to singly linked list, and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both directions.
- In doubly linked list insertion or deletion of any node, whose address is given, can be carried out in constant number of operations and on the other hand in singly linked list the same operation would require the address of the predecessor’s address which of course is not a problem with doubly linked list as we can move in both directions.

The below figure show how a doubly linked list looks like :

Let’s now directly jump over to various operations which can be performed over doubly linked list:

- Add a node in a list at beginning or at end or in between.
- Delete a node from list at specific location.
- Reverse a list.
- Count nodes present in the list.
- Print the list to see all the nodes present in the list.

First let’s have a look at the node definition :

struct node{ int data; struct node *prev; struct node *next; };

It’s evident from the above node definition that a node in a doubly linked list have 2 links (** next **and

**) and one data value (**

*prev***).**

*data***Add a node in a list.**

Insertion of a node in a linked list can be done at three places, viz. at start, in between at a specified location or at end.- Inserting a node at the start of list :

**Algorithm :**- Update the
pointer of the new node to the head node and make*next*pointer of the new node as NULL**prev** - Now update head node’s
pointer to point to new node and make new node as head node.*prev*

- Update the
- Inserting a node in between of list :

**Algorithm :**- Traverse the list to the position where the new node is to be inserted.Let’s call this node as Position Node (we have to insert new node just next to it).
- Make the
pointer of new pointer to point to next node of position node. Also make the*next*point of new node to point to position node.*prev* - Now point position node’s
pointer to new node and*next*node of next node of position node to point to new node.*prev*

- Inserting a node at the end of the list :

**Algorithm :**- Traverse the list to end. Let’s call the current last node of list as Last node.
- Make
pointer of New node to point to NULL and*next*pointer of new node to point to Last node.*prev* - Update next pointer of Last node to point to new Node.

Thus we see how easily we can add a node in a list. Let us now write code for all the three cases.Please note here that we are passing double pointer in the function as we may require to change the head pointer.

void AddNode(struct node **head, int position, int value) { int currentNodePosition=1; struct node *temp, *newNode; newNode = (struct node *)malloc(sizeof(struct node)); if(*head == NULL) { printf("\nList Empty."); position=1; } if(!newNode) { printf("\nError while allocating memory to new Node"); return; } newNode->data = value; if(position==1) { printf("\nInserting node at the beginning of the list"); newNode->next = *head; newNode->prev = NULL; //*head->prev = newNode; *head = newNode; return; } temp = *head; while((currentNodePosition<position-1)&& (temp->next!=NULL)) { temp = temp->next; currentNodePosition++; } if(temp->next==NULL) { printf("\nInserting node at the last."); newNode->next = temp->next; newNode->prev = temp; temp->next = newNode; } else { printf("\nInserting node at position : %d",position); newNode->next = temp->next; newNode->prev = temp; temp->next->prev = newNode; temp->next = newNode; return; } }

- Inserting a node at the start of list :
**Delete a node from a list.**As similar to Insertion of a node in a linked list, deletion can also be done at three places, viz. from start, in between at a specified location or from end.

- Deletion of node from start of list :

**Algorithm :**- Create a temporary node which will point to the same node where Head pointer is pointing.
- Now move the head pointer to point to the next node. Also change the heads
to NULL. Then dispose off the node pointed by temporary node.*prev*

- Deletion of node from end of list :

**Algorithm :**- Traverse the list till end. While traversing maintain the previous node address also. Thus when we reach at end then we have one pointer pointing to NULL and other pointing to penultimate node.
- Update the
pointer of penultimate node to point to NULL.*next* - Dispose off the Last Node.

- Deletion of node from an intermediate position :

**Algorithm :**- As similar to previous case maintain two pointer, one pointing to the node to be deleted and other to the node previous to our target node (Node to be deleted).
- Once we reach our target node, change previous node
pointer to point to**next**pointer of target node and make**next**pointer of next node of target node to point to previous node of target node.*prev* - Dispose off the target node.

I know there is a lot of confusion in the algorithm. To clear the confusion have a look at the code part below.

void DeleteNodeFromList(struct node **head, int position) { struct node *temp, *temp2; temp = *head; int currentNodePosition = 1; if(*head == NULL) { printf("\nList is empty"); return; } if(position == 1) { temp = temp->next; if(*head != NULL) { temp->prev = NULL; } free(temp); return; } while((currentNodePosition<position)&& (temp->next!=NULL)) { printf("\nDeleting node from starting"); temp = temp->next; currentNodePosition++; } if(temp->next == NULL) { printf("\nDeleting node from last"); temp2 = temp->prev; temp2->next = NULL; free(temp); return; } else { temp2 = temp->prev; temp2->next = temp->next; temp->next->prev = temp2; free(temp); return; } }

- Deletion of node from start of list :
**Reversing a list.**This is one of the favorite question which interviewer is bound to ask while interviewing a candidate on data structures. There are many ways to accomplish this but we will explain the way we implemented in our example.

**Algorithm :**- First swap
and**prev**pointer of all nodes.**next** - Point head to the tail node as tail node is now our new head node.

This method is pretty straight forward and fast also. Below is the code snippet of reversing a Doubly Linked List.

void ReverseList(struct node **head) { struct node *temp, *temp2; temp = *head; temp2 = NULL; while(temp != NULL) { temp2 = temp->next; temp->next = temp->prev; temp->prev = temp2; if(temp->prev == NULL) { *head = temp; } temp = temp->prev; } }

- First swap
**Counting nodes in list/ Printing content of list.**

This one is the easiest operation on Doubly Linked List. All what you have to do is to traverse the list and while traversing you need to keep on increment counter (while counting nodes in list)/ you need to print the data of each node (while printing the nodes). The code snippets are as below :void PrintList(struct node ** head) { struct node *temp; temp = *head; if(temp == NULL) { printf("List is empty"); return; } while(temp->next != NULL) { printf("%d <==>",temp->data); temp= temp->next; } printf("%d",temp->data); return; } void CountNodesInList(struct node ** head) { struct node *temp; int numberOfNodes = 1; temp = *head; if(temp == NULL) { printf("\nList is empty"); return; } while(temp->next != NULL) { temp= temp->next; numberOfNodes++; } if(numberOfNodes==1) { printf("\nThere is %d node in the list.",numberOfNodes); } else { printf("\nThere are %d node/s in the list.",numberOfNodes); } return; }

Those were the major operations which can be performed on a Doubly Linked List. Please find the complete code snippet here. Visit idlebrains for more tutorials on data structures. Visit singly linked list to refresh your memories with your very own singly linked list.

I wish you learn with as much fun as i did while writing this article. Do post your suggestions, doubts, or comments. Keep an eye on idlebrains for much more and Stay tuned with us.

Can u plz tell me the program to merge two doubly linked list in c code . Plz reply

Can you please elaborate on what parameters you want to merge the 2 lists.

I will right away seize your rss feed as I can not to find your e-mail subscription link or e-newsletter service. Do you’ve any? Kindly allow me know in order that I may just subscribe. Thanks.

Hi Carmin Abrag,

Here is our RSS Feed – http://feeds.feedburner.com/IdleBrains

thanku for the detailed explanation

Thanks Radhu for dropping by 🙂 We are glad that you liked the article.. 🙂

IT IS REALLY VERY USEFUL IN SHORT .

good mornign sir.

I have seen your interesting tutorial about the double linked list.

Functions are ok but i don’t know how to run this program ,pratically into the main i try to do something but it doesn’t works .Your link “Please find the complete code snippet here” doesn’t work , no page opening when i click on it .

Could you please tell me what to do ?

Thanks a lot

Regards

Walter