Insertion in doubly linked list

Insertion in doubly linked list can be done at any location.  The new node can be added at the beginning, at the end, after a given node or at a given position. Whenever Insertion of a new node is done in a doubly linked list it requires updating pointers of the previous and next node along with the pointer of the new node.

Insertion in doubly linked list at the beginning

The insertion of a new node at the beginning is the easiest insertion operation. The FIRST pointer (storing address of first node) is referred to do this addition. These four pointer updates will do the insertion at the beginning

1. The NEXT pointer of the new node is updated with the value of FIRST pointer.
2. The PREV pointer of the node referred by FIRST pointer  is updated with address of new node
3. The PREV pointer of the new node is set to NULL.
4. FIRST pointer is set to address of new node.

Insertion at the End

The insertion of a new node at the end of the doubly linked list is also as simple as adding a new node at the beginning. The LAST pointer is referred to do this addition. These four pointer updates will do the insertion at the end of a doubly linked list.

1. The NEXT pointer of the new node is updated with NULL.
2. The PREV pointer of the new node is set to the value of LAST pointer.
3. The NEXT pointer of the node referred by LAST pointer  is updated with address of new node.
4. LAST pointer is set to address of the new node.

Insertion after a Node with given value

The insertion of a new node after a node with given value involves search process to first find the address of the specified node. The search process returns the address of this node in LOC pointer. These four pointer updates will complete the task

1. The PREV pointer of the node referred by NEXT pointer of the LOC pointer  is updated with address of new node.
2. The NEXT pointer of the new node is updated with NEXT pointer of LOC.
3. The PREV pointer of the new node is set to the value of LOC pointer.
4. The NEXT pointer of the node referred by LOC pointer  is updated with address of new node.

Insertion at k^th Position

The insertion of a new node k^th position involves traversal process to count the nodes traversed. While traversing the address of the previous node is maintained in a pointer, say, TEMP.   When the count of traversed nodes becomes equal to K, traversal is terminated and the new node is inserted after TEMP with these pointer updates.

1. The PREV pointer of the node referred by NEXT pointer of the TEMP pointer  is updated with address of new node.
2. The NEXT pointer of the new node is updated with NEXT pointer of TEMP.
3. The PREV pointer of the new node is set to the value of TEMP pointer.
4. The NEXT pointer of the node referred by TEMP pointer  is updated with address of new node.

admin