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 is called a doubly linked list. The node data, the pointer to the next node in sequence (next pointer), and the pointer to the previous node (previous pointer) are the three parts of a node, in a doubly-linked list.
Structure of a node in a doubly-linked list in C:
struct node { struct node *prev; int data; struct node *next; } |
The null indicating end in each direction is included in the prev part of the first node and the next part of the last node always. In a singly linked list, each node contains the address of the next node but doesn’t have any record of its previous nodes. Thus, we can traverse only in one direction, in a singly linked list. To overcome this limitation of a singly linked list, each node of the doubly linked list contains the address of its previous node. Hence, we can use the previous address stored inside the previous part of each node to find the details about the previous node.
Memory Representation of a doubly-linked list:
A doubly linked list causes more expansive basic operations such as insertion and deletion because it consumes more space for every node. But, since the list maintains pointers in both the directions i.e., both forward and backwards, we can easily manipulate the elements of the list.
Operations on a doubly-linked list:
Node Creation:
{ struct node *prev; int data; struct node *next; }; struct node *head; |
The other operations of the doubly linked list are described below.
| SN | Operation | Uses |
| 1 | Insertion at beginning | To add a node at the beginning of a linked list. |
| 2 | Insertion at end | To add a node at the end of a linked list. |
| 3 | Insertion after specified node | To add a node in a linked list after the specified node. |
| 4 | Deletion at beginning | To remove a node from the beginning of a linked list. |
| 5 | Deletion at the end | To remove a node from the end of a linked list. |
| 6 | Deletion of the node having given data | To remove a node which is present just after the node containing the given data. |
| 7 | Searching | To compare each node data with the item to be searched. It returns the location of the item in the list, if the item is found. Else it returns null. |
| 8 | Traversing | To visit each node of a linked 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 the doubly linked list:
#include<stdio.h> #include<stdlib.h> struct node { struct node *prev; struct node *next; int data; }; struct node *head; void insertionAtBeginning(); void insertionAtLast(); void insertionAtSpecified(); void deletionAtBeginning(); void deletionAtLast(); void deletionAtSpecified(); void show(); void search(); void main() { int choice =0; while(choice != 9) { printf("\n*********Main Menu*********\n"); printf("\nChoose any option from the below list.\n"); printf("\n................................................\n"); printf("\n1.Insert at Beginning\n2.Insert at Last\n3.Insert at any random location\n4.Delete from Beginning\n5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n"); printf("\nEnter your choice:\n"); scanf("\n%d",&choice); switch(choice) { case 1: insertionAtBeginning(); break; case 2: insertionAtLast(); break; case 3: insertionAtSpecified(); break; case 4: deletionAtBeginning(); break; case 5: deletionAtLast(); break; case 6: deletionAtSpecified(); break; case 7: search(); break; case 8: show(); break; case 9: exit(0); break; default: printf("Please enter a valid choice.\n"); } } } void insertionAtBeginning() { struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter the element to insert:\n"); scanf("%d",&item); if(head==NULL) { ptr->next = NULL; ptr->prev=NULL; ptr->data=item; head=ptr; } else { ptr->data=item; ptr->prev=NULL; ptr->next = head; head->prev=ptr; head=ptr; } printf("\nNode inserted successfully!!\n"); } } void insertionAtLast() { struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter the element to insert:\n"); scanf("%d",&item); ptr->data=item; if(head == NULL) { ptr->next = NULL; ptr->prev = NULL; head = ptr; } else { temp = head; while(temp->next!=NULL) { temp = temp->next; } temp->next = ptr; ptr ->prev=temp; ptr->next = NULL; } } printf("\nNode inserted successfully!!\n"); } void insertionAtSpecified() { struct node *ptr,*temp; int item,loc,i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\n OVERFLOW"); } else { temp=head; printf("\nEnter the location:\n"); scanf("%d",&loc); for(i=0;i<loc;i++) { temp = temp->next; if(temp == NULL) { printf("\nLess than %d elements", loc); return; } } printf("\nEnter the element to insert:\n"); scanf("%d",&item); ptr->data = item; ptr->next = temp->next; ptr -> prev = temp; temp->next = ptr; temp->next->prev=ptr; printf("\nNode inserted successfully!!\n"); } } void deletionAtBeginning() { struct node *ptr; if(head == NULL) { printf("\n UNDERFLOW"); } else if(head->next == NULL) { head = NULL; free(head); printf("\nNode deleted successfully!!\n"); } else { ptr = head; head = head -> next; head -> prev = NULL; free(ptr); printf("\nNode deleted successfully!!\n"); } } void deletionAtLast() { struct node *ptr; if(head == NULL) { printf("\n UNDERFLOW"); } else if(head->next == NULL) { head = NULL; free(head); printf("\nNode deleted successfully!!\n"); } else { ptr = head; if(ptr->next != NULL) { ptr = ptr -> next; } ptr -> prev -> next = NULL; free(ptr); printf("\nNode deleted successfully!!\n"); } } void deletionAtSpecified() { struct node *ptr, *temp; int val; printf("\nEnter the element after which the node is to be deleted:\n"); scanf("%d", &val); ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) { printf("\nCan't delete\n"); } else if(ptr -> next -> next == NULL) { ptr ->next = NULL; } else { temp = ptr -> next; ptr -> next = temp -> next; temp -> next -> prev = ptr; free(temp); printf("\nNode deleted successfully!!\n"); } } void show() { struct node *ptr; printf("\nList:\n"); ptr = head; while(ptr != NULL) { printf("%d\n",ptr->data); ptr=ptr->next; } } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf("\nEmpty List!!\n"); } else { printf("\nEnter element to search:\n"); scanf("%d",&item); while (ptr!=NULL) { if(ptr->data == item) { printf("\nElement found at location %d ",i+1); flag=0; break; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf("\nElement not found.\n"); } } } |
Output:
*********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 1 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 2 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 location: 1 Enter the element to insert: 3 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 4 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 5 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 location: 3 Enter the element to insert: 6 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 4 1 2 3 6 5 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 1 2 3 6 5 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 1 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 1 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 element to search: 2 Element not found. *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 1 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 2 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 3 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 the element to insert: 4 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 location: 3 Enter the element to insert: 5 Node inserted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 2 1 1 3 5 4 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 element after which the node is to be deleted: 3 Node deleted successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 2 1 1 3 4 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 element to search: 3 Element found at location 4 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 successfully!! *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 List: 2 *********Main Menu********* Choose any option from the below list. ................................................ 1.Insert at Beginning 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 |