Doubly Linked List

Disadvantages of Singly Linked List:

• We can traverse list from only one direction i.e. forward direction.
• Reverse operation is difficult in singly linked list.  
• It is not easy to sort the elements stored in the linear linked list

Doubly Linked List:

 

• We are aware that the singly linked list is a collection of nodes with each node having a data part and a pointer pointing to the next node.  
  
• A doubly linked list is also a collection of nodes
• Each node here consists of a data part and two pointers. 
• One pointer points to the previous node while the second pointer points to the next node.    
• As in the singly linked list, the doubly linked list also has a head and a (tail) last node.  
  
• The previous pointer of the head is set to NULL as this is the first node. The next pointer of the (tail) last node is set to NULL as this is the last node. 

 

 

Structure of DLL node: 

class node{

data_type data;

node * next;             

Node *previous;

}

Doubly Linked list as an ADT:

Following are some of the operations that we can perform on a doubly linked list:

• Insertion

Insertion operation of the doubly linked list inserts a new node (temp) in the linked list. Depending on the position where the new node is to be inserted, we can have the following insert operations.

• Insertion at front – Inserts a new node as the first node.

• Insertion at the end – Inserts a new node at the end as the last node.

• Insertion before a node – Given a node, inserts a new node before this node.

• Deletion

Deletion operation deletes a node from a given position in the doubly linked list.

• Deletion of the first node – Deletes the first node in the list

• Deletion of the last node – Deletes the last node in the list.

• Deletion of a node given the data – Given the data, the operation matches the data with the node data in the linked list and deletes that node. 

• Traversal

Traversal is a technique of visiting each node in the linked list. In a doubly linked list, we have two types of traversals as we have two pointers with different directions in the doubly linked list. 

Forward traversal – Traversal is done using the next pointer which is in the forward direction. Backward traversal – Traversal is done using the previous pointer which is the backward direction

• Reverse

This operation reverses the nodes in the doubly linked list so that the first node becomes the last node while the last node becomes the first node.