Double linked list

A Doubly Linked List (DLL) is a linked data structure consists of a set of sequentially linked records called nodes which contains a lot of data elements and is even able to do a lot of operations such as insertion, delete, remove and add.

Implementation of Double linked list:
So to start with, we need to define the node in whatever language you are comfortable with. I am really comfortable with C++ language. So I have given all the information in C++ language over here.

After defining the node what I have done is I have defined double linked list class with the following methods:

add_front: Adds a new node at the beginning of the list
add_after: Adds a new node after another node
add_before: Adds a new node before another node
add_end: Adds a new node at the end of the list
delete: Removes the node
forward_traverse: Traverse the list in the forward direction
backward_traverse: Traverse the list in the backward direction

Insert Data in the beginning:
So if we want to add data in the beginning then what we should do is that the previous pointer of the first node should always be NULL and the next will point to the front. When the node is inserted it becomes the first node of the list then we make front and endpoint to this node or else we only make front point to this node.

Insert Data before a node:
Let's say we want to add X before Y then what we will do is X’s next pointer will point to Y and X’s prev pointer will point the node Y’s prev pointer is pointing. And Y’s prev pointer will now point to X. We need to make sure that if Y is the first node of list then after adding X we make front point to X.

Insert Data after the Node:
Let's say we want to add Y after X then what we will do is Y’s prev pointer will point to X and Y’s next pointer will point the node X’s next pointer is pointing. And X’s next pointer will now point to Y. We need to make sure that if X is the last node of list then after adding Y we make end point to Y.

Insert data in the end:
The next pointer of the last node will always be NULL and prev will point to the end. If the node is inserted is the first node of the list then we make front and endpoint to this node. Else we only make endpoint to this node.

Remove Node:
It removes the specified node from the Doubly Linked List.

Forward transversal:
It starts with the front node and visits all the nodes until the node becomes NULL.

Backward Transversal:
It starts with the end node and visits all the nodes until the node becomes NULL.

Advantages:
1) A DLL can be traversed in both forward and backward directions.
2) The delete operation in DLL is more efficient if the pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node. In DLL, we can get the previous node using the previous pointer.

Disadvantages:
1) Every node of DLL Requires extra space for a previous pointer.
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with the next pointers. For example in the following functions for insertions at different positions, we need 1 or 2 extra steps to set the previous pointer.