Doubly Linked Lists and Its Applications

Doubly Linked List

Doubly linked list (also called two-way linked list) has an advantage from a singly linked list that, given a node in the list, we can navigate in both the directions. A node in a singly linked list cannot be removed unless we have the pointer to its predecessor. But in doubly linked list, we can delete a node even if we don't have previous node address (since, each node has left pointer pointing to previous node and can move backward). The primary disadvantages, however, of doubly linked list are:

• Each node requires an extra pointer, requring more space
• The insertion or deletion of a node takes a bit longer due to more pointer operations

Structure Implementation

struct doublyNode{

int data;

struct doublyNode *next;

struct doublyNode *prev;

};

Doubly Linked List Insertion

Insertion before the head

In this case, new node is inserted before the head node. Previous and next pointers need to be modified and it can be done in two steps:

• Update the right pointer of new node to point to the current head node (dotted link in below figure) and also make left pointer ot new node as NULL

• Update head node's left pointer to point to the new node and make new node as head.

Insertion at the End

In this case, traverse the list till the end and insert the new node.

• New node right pointer points to NULL and left pointer points to the end of the list

• Update right of pointer of last node to point to new node

Insertion at the Middle

As discussed in singly linked lists, traverse the list till the position node and insert the new node.

• New node right pointer points to the next node of the position node where we want to insert the new node. Also, new node left pointer points to the position node.

• Position node right pointer points to the new node and the next node of position nodes left pointer points to new node

Doubly Linked List Deletion

Deleting the first node

In this case, first node (current node head) is removed from the list. It can be done in two steps:

• Create a temporary node which will point to same node as that of the head.

• Now, move the head node's pointer to the next node and change the head's left pointer to NULL. Then, dispose the temporary node.

Deleting the last node

This operation is a bit trickier, because the algorithm has to find a node, which is previous to the tail. This can be done in three steps.

• Traverse the list and while traversing maintain the previous node address also. Ny the time we reach the end of list, we will have two pointers, one pointing to the NULL (tail) and other pointing to the node before tail node.

• Update tail node's previous node's next pointer with NULL

• Dispose the tail node

Deleting an Intermediate Node

• As similar to previous case, maintain previous node also while traversing the list. Once we found the node to be deleted, change the previous node's next pointer to the next node of the node to be deleted.

• Dispose the current node to be deleted.

Applications of Doubly Linked List