What is Doubly Linked List ? - data structure tutorial

What is Doubly Linked List ? - data structure tutorial

It is strongly recommended that you must have knowledge of linked lists before. If you dont have any knowledge of linked list then click in this link .

Doubly Linked List is a variety of Linked list wherein navigation is possible in the two different ways, either forward and backward effectively as compared with Single Linked List.

Therefore, in a doubly-linked list, a node comprises of three sections: node information, a pointer to the next node (next pointer), a pointer to the previous node (past pointer).

A doubly linked list containing three nodes having numbers from 1 to 3 in their information part, is shown below.

Advantages over the singly linked list

1) A DLL can be navigated in both forward and reverse way.

2) The deletion operation in DLL is more effective if a pointer to the node to be deleted is given.

   In a singly linked list, to delete a node, a pointer to the previous node is required.

   To get this past node, here and there the list is traversed.

   In DLL, we can get the previous node by utilizing previous pointer.

3) We can rapidly add another node before a given node (

Disadvantages of over singly Linked List

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

Basic Operations

The following are the basic operations supported by a list.

Insertion Operation

A node can be added in four ways

Add a node at the front

Add a node after a given node

3) Add a node at the end

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
 
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Add a node before a given node

/* Given a node as next_node, insert a new node before the given node */
void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data) 
{ 
 /*1. check if the given next_node is NULL */
 if (next_node == NULL) { 
  printf("the given next node cannot be NULL"); 
  return; 
 } 

 /* 2. allocate new node */
 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

 /* 3. put in the data */
 new_node->data = new_data; 

 /* 4. Make prev of new node as prev of next_node */
 new_node->prev = next_node->prev; 

 /* 5. Make the prev of next_node as new_node */
 next_node->prev = new_node; 

 /* 6. Make next_node as next of new_node */
 new_node->next = next_node; 

 /* 7. Change next of new_node's previous node */
 if (new_node->prev != NULL) 
  new_node->prev->next = new_node; 
 /* 8. If the prev of new_node is NULL, it will be 
 the new head node */
 else
  (*head_ref) = new_node; 
 
}

Deletion Operation

A node can be added in 2 ways:

Delete a node from beginning of a Doubly Linked List

1. void beginning_delete()  
2. {  
3.     struct node *ptr;  
4.     if(head == NULL)  
5.     {  
6.         printf("\n UNDERFLOW\n");  
7.     }  
8.     else if(head->next == NULL)  
9.     {  
10.         head = NULL;   
11.         free(head);  
12.         printf("\nNode Deleted\n");  
13.     }  
14.     else  
15.     {  
16.         ptr = head;  
17.         head = head -> next;  
18.         head -> prev = NULL;  
19.         free(ptr);  
20.         printf("\nNode Deleted\n");  
21.     }  
22. }

Deletion in doubly linked list at the end

1. void last_delete()  
2. {  
3.     struct node *ptr;  
4.     if(head == NULL)  
5.     {  
6.         printf("\n UNDERFLOW\n");  
7.     }  
8.     else if(head->next == NULL)  
9.     {  
10.         head = NULL;   
11.         free(head);  
12.         printf("\nNode Deleted\n");  
13.     }  
14.     else   
15.     {  
16.         ptr = head;   
17.         if(ptr->next != NULL)  
18.         {  
19.             ptr = ptr -> next;   
20.         }  
21.         ptr -> prev -> next = NULL;   
22.         free(ptr);  
23.         printf("\nNode Deleted\n");  
24.     }  
25. }

Some commonly asked problems on doubly linked lists in interviews (What is Doubly Linked List ? - data structure tutorial):

1. WAP to find middle element of a doubly linked list.
2. WAP to find pair with given sum in a doubly linked list.
3. WAP to reverse a doubly linked list.

What is Doubly Linked List ? - data structure tutorial

Contact Form