Doubly linked list

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node   
2. {  
3.     struct node *prev;   
4.     int data;  
5.     struct node *next;   
6. }   

The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.

In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list. Due to the fact that, each node of the list contains the address of its previous node, we can find all the details about the previous node as well by using the previous address stored inside the previous part of each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image. Generally, doubly linked list consumes more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head pointer points to the starting address 1. Since this is the first element being added to the list therefore the prev of the list contains null. The next node of the list resides at address 4 therefore the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next part.

Operations on doubly linked list

Node Creation

1. struct node   
2. {  
3.     struct node *prev;  
4.     int data;  
5.     struct node *next;  
6. };  
7. struct node *head;   

All the remaining operations regarding doubly linked list are described in the following table.

SN	Operation	Description
1	Insertion at beginning	Adding the node into the linked list at beginning.
2	Insertion at end	Adding the node into the linked list to the end.
3	Insertion after specified node	Adding the node into the linked list after the specified node.
4	Deletion at beginning	Removing the node from beginning of the list
5	Deletion at the end	Removing the node from end of the list.
6	Deletion of the node having given data	Removing the node which is present just after the node containing the given data.
7	Searching	Comparing each node data with the item to be searched and return the location of the item in the list if the item found else return null.
8	Traversing	Visiting each node of the list at least once in order to perform some specific operation like searching, sorting, display, etc.

Menu Driven Program in C to implement all the operations of doubly linked list

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. struct node  
4. {  
5.     struct node *prev;  
6.     struct node *next;  
7.     int data;  
8. };  
9. struct node *head;  
10. void insertion_beginning();  
11. void insertion_last();  
12. void insertion_specified();  
13. void deletion_beginning();  
14. void deletion_last();  
15. void deletion_specified();  
16. void display();  
17. void search();  
18. void main ()  
19. {  
20. int choice =0;  
21.     while(choice != 9)  
22.     {  
23.         printf("\n*********Main Menu*********\n");  
24.         printf("\nChoose one option from the following list ...\n");  
25.         printf("\n===============================================\n");  
26.         printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n  
27.         5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");  
28.         printf("\nEnter your choice?\n");  
29.         scanf("\n%d",&choice);  
30.         switch(choice)  
31.         {  
32.             case 1:  
33.             insertion_beginning();  
34.             break;  
35.             case 2:  
36.                     insertion_last();  
37.             break;  
38.             case 3:  
39.             insertion_specified();  
40.             break;  
41.             case 4:  
42.             deletion_beginning();  
43.             break;  
44.             case 5:  
45.             deletion_last();  
46.             break;  
47.             case 6:  
48.             deletion_specified();  
49.             break;  
50.             case 7:  
51.             search();  
52.             break;  
53.             case 8:  
54.             display();  
55.             break;  
56.             case 9:  
57.             exit(0);  
58.             break;  
59.             default:  
60.             printf("Please enter valid choice..");  
61.         }  
62.     }  
63. }  
64. void insertion_beginning()  
65. {  
66.    struct node *ptr;   
67.    int item;  
68.    ptr = (struct node *)malloc(sizeof(struct node));  
69.    if(ptr == NULL)  
70.    {  
71.        printf("\nOVERFLOW");  
72.    }  
73.    else  
74.    {  
75.     printf("\nEnter Item value");  
76.     scanf("%d",&item);  
77.       
78.    if(head==NULL)  
79.    {  
80.        ptr->next = NULL;  
81.        ptr->prev=NULL;  
82.        ptr->data=item;  
83.        head=ptr;  
84.    }  
85.    else   
86.    {  
87.        ptr->data=item;  
88.        ptr->prev=NULL;  
89.        ptr->next = head;  
90.        head->prev=ptr;  
91.        head=ptr;  
92.    }  
93.    printf("\nNode inserted\n");  
94. }  
95.      
96. }  
97. void insertion_last()  
98. {  
99.    struct node *ptr,*temp;  
100.    int item;  
101.    ptr = (struct node *) malloc(sizeof(struct node));  
102.    if(ptr == NULL)  
103.    {  
104.        printf("\nOVERFLOW");  
105.    }  
106.    else  
107.    {  
108.        printf("\nEnter value");  
109.        scanf("%d",&item);  
110.         ptr->data=item;  
111.        if(head == NULL)  
112.        {  
113.            ptr->next = NULL;  
114.            ptr->prev = NULL;  
115.            head = ptr;  
116.        }  
117.        else  
118.        {  
119.           temp = head;  
120.           while(temp->next!=NULL)  
121.           {  
122.               temp = temp->next;  
123.           }  
124.           temp->next = ptr;  
125.           ptr ->prev=temp;  
126.           ptr->next = NULL;  
127.           }  
128.              
129.        }  
130.      printf("\nnode inserted\n");  
131.     }  
132. void insertion_specified()  
133. {  
134.    struct node *ptr,*temp;  
135.    int item,loc,i;  
136.    ptr = (struct node *)malloc(sizeof(struct node));  
137.    if(ptr == NULL)  
138.    {  
139.        printf("\n OVERFLOW");  
140.    }  
141.    else  
142.    {  
143.        temp=head;  
144.        printf("Enter the location");  
145.        scanf("%d",&loc);  
146.        for(i=0;i<loc;i++)  
147.        {  
148.            temp = temp->next;  
149.            if(temp == NULL)  
150.            {  
151.                printf("\n There are less than %d elements", loc);  
152.                return;  
153.            }  
154.        }  
155.        printf("Enter value");  
156.        scanf("%d",&item);  
157.        ptr->data = item;  
158.        ptr->next = temp->next;  
159.        ptr -> prev = temp;  
160.        temp->next = ptr;  
161.        temp->next->prev=ptr;  
162.        printf("\nnode inserted\n");  
163.    }  
164. }  
165. void deletion_beginning()  
166. {  
167.     struct node *ptr;  
168.     if(head == NULL)  
169.     {  
170.         printf("\n UNDERFLOW");  
171.     }  
172.     else if(head->next == NULL)  
173.     {  
174.         head = NULL;   
175.         free(head);  
176.         printf("\nnode deleted\n");  
177.     }  
178.     else  
179.     {  
180.         ptr = head;  
181.         head = head -> next;  
182.         head -> prev = NULL;  
183.         free(ptr);  
184.         printf("\nnode deleted\n");  
185.     }  
186.   
187. }  
188. void deletion_last()  
189. {  
190.     struct node *ptr;  
191.     if(head == NULL)  
192.     {  
193.         printf("\n UNDERFLOW");  
194.     }  
195.     else if(head->next == NULL)  
196.     {  
197.         head = NULL;   
198.         free(head);   
199.         printf("\nnode deleted\n");  
200.     }  
201.     else   
202.     {  
203.         ptr = head;   
204.         if(ptr->next != NULL)  
205.         {  
206.             ptr = ptr -> next;   
207.         }  
208.         ptr -> prev -> next = NULL;   
209.         free(ptr);  
210.         printf("\nnode deleted\n");  
211.     }  
212. }  
213. void deletion_specified()  
214. {  
215.     struct node *ptr, *temp;  
216.     int val;  
217.     printf("\n Enter the data after which the node is to be deleted : ");  
218.     scanf("%d", &val);  
219.     ptr = head;  
220.     while(ptr -> data != val)  
221.     ptr = ptr -> next;  
222.     if(ptr -> next == NULL)  
223.     {  
224.         printf("\nCan't delete\n");  
225.     }  
226.     else if(ptr -> next -> next == NULL)  
227.     {  
228.         ptr ->next = NULL;  
229.     }  
230.     else  
231.     {   
232.         temp = ptr -> next;  
233.         ptr -> next = temp -> next;  
234.         temp -> next -> prev = ptr;  
235.         free(temp);  
236.         printf("\nnode deleted\n");  
237.     }     
238. }  
239. void display()  
240. {  
241.     struct node *ptr;  
242.     printf("\n printing values...\n");  
243.     ptr = head;  
244.     while(ptr != NULL)  
245.     {  
246.         printf("%d\n",ptr->data);  
247.         ptr=ptr->next;  
248.     }  
249. }   
250. void search()  
251. {  
252.     struct node *ptr;  
253.     int item,i=0,flag;  
254.     ptr = head;   
255.     if(ptr == NULL)  
256.     {  
257.         printf("\nEmpty List\n");  
258.     }  
259.     else  
260.     {   
261.         printf("\nEnter item which you want to search?\n");   
262.         scanf("%d",&item);  
263.         while (ptr!=NULL)  
264.         {  
265.             if(ptr->data == item)  
266.             {  
267.                 printf("\nitem found at location %d ",i+1);  
268.                 flag=0;  
269.                 break;  
270.             }   
271.             else  
272.             {  
273.                 flag=1;  
274.             }  
275.             i++;  
276.             ptr = ptr -> next;  
277.         }  
278.         if(flag==1)  
279.         {  
280.             printf("\nItem not found\n");  
281.         }  
282.     }     
283.           
284. }  

Output

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value12

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value1234

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
2

Enter value89

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
3
Enter the location1
Enter value12345

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12345
12
89

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
5

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123
12345

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
7

Enter item which you want to search?
123

item found at location 1 
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

Can't delete

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
9 

Exited..