If I am not wrong, we had an introduction and implementation of Linked List in the earlier posts! If you have not gone through it yet, the links are provided in the section, “Reference and Recommendations”. So, taking the discussion of linked lists a little ahead we will now raise a question. 

Can there be a way of overcoming the complexity of reverse traversal in the linked list? In a linked list we link the nodes in one direction only. Why can’t we do a two-way connection? Yes, we can. This is what a double-connection. Well in the linked list it is known as Doubly Linked List. How do we do that is quite simple and we shall see that now!!

Doubly Linked List:

Structure:

As we can observe, there is an extra pointer prev (previous) which points to the previous node. The functionality of data, head, and next are the same as that of the Singly Linked List or Simple Linked List. The previous of first and next of last nodes point to null as there aren’t any nodes before or after those nodes respectively.

Operations on DLL:

Insertion at the beginning:

Step 1: Find the node at the beginning of the list. 

Step 2: Point the previous of the beginning node (A) to the next of the new node (D). 

Step 3: Point the previous of the new node (D)  to null as it should be the first node.

Step 4: Make the head pointer point to the new node to identify the beginning of the first node in the traversal.

Here step 2 and step 3 can be interchanged as the nodes have a double connection.

Insert before or after any node:

Step 1: Find the position where the node has to be inserted in the created doubly Linked List. Let’s suppose that the node has to be inserted after A or before B.

Step 2: Point the next of new node (D) to the previous of next node (B). And point the previous of new node (D) to the next of previous node (A).

Step 3: Point the next of A to the previous of D and the previous of B to the next of D.

Hence the insertion is done.

Insertion at the end:

The insertion at the end of the list could be simple as the above are explained. Find the end node of the list and this can be found where the next of the node points to null. In the above cases, node C is the last node as the next of the C is null. 

We have to point the next of the last node C to the previous of the new node(say D) and the previous of the new node D to the next of the last node C. The final part involves pointing the next of new node D to null. Hence it is done.

Saying that it is quite simple, the procedure has been already explained.

Deletion:

Step 1: Find the position of the node which has to be deleted (B) from the list.

Step 2: Point the previous of the next node (C) to the node which has to be deleted (B) to the next of the previous (A) node to the node to be deleted (B).

Step 3: Point the next of the node A to the previous of node B.

Hence deletion is performed on the doubly linked list.

Download the code for the implementation of DLL in C

Advantages:

1. The traversal in a doubly-linked list is bidirectional that makes reversing the list easier.
2. The delete operation is more efficient if the pointer to the node to be deleted is given.

Disadvantages:

1. It consumes extra memory space compared to the array and singly linked list.
2. Direct access of the elements is not possible as the nodes are arranged randomly in the memory. Only sequential access of elements is possible.

Applications:

1. Used to represent the game deck of cards.
2. Binary trees, stacks, and Hash tables are constructed using doubly-linked lists.
3. Can be used in browsers or anywhere where two-way navigation is required i.e. front and back.
4. It is used to perform undo and redo operations in many applications.

References and Recommendations:

• Array and Linked List
• Implementation of Linked List in C
• Binary Trees
• Representation of binary trees using arrays