Doubly Linked List in Data Structure

Following are the types of Linked List

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Doubly Circular Linked List

2. Doubly Linked List

• Doubly linked list is a sequence of elements in which every node has link to its previous node and next node.
• Traversing can be done in both directions and displays the contents in the whole list.

In the above figure, Link1 field stores the address of the previous node and Link2 field stores the address of the next node. The Data Item field stores the actual value of that node. If we insert a data into the linked list, it will be look like as follows:

Important Note: 
First node is always pointed by head. In doubly linked list, previous field of the first node is always NULL (it must be NULL) and the next field of the last must be NULL.

In the above figure we see that, doubly linked list contains three fields. In this, link of two nodes allow traversal of the list in either direction. There is no need to traverse the list to find the previous node. We can traverse from head to tail as well as tail to head.

Advantages of Doubly Linked List

• Doubly linked list can be traversed in both forward and backward directions.
• To delete a node in singly linked list, the previous node is required, while in doubly linked list, we can get the previous node using previous pointer.
• It is very convenient than singly linked list. Doubly linked list maintains the links for bidirectional traversing.

Disadvantages of Doubly Linked List

• In doubly linked list, each node requires extra space for previous pointer.
• All operations such as Insert, Delete, Traverse etc. require extra previous pointer to be maintained.

Output: