Inserting a Node in Doubly Linked List

This article is part of article series - "Datastructures"

Previous Article: Doubly Linked List                                           Next Article: Deletion of a Node from Doubly Linked List.

Insertion of a Node

Before we discuss about how to insert a NODE let us discuss few rules to follow at the time of insertion.

• Check the location into which the user want to insert a new NODE. The possible locations where an user can insert a new node is in the range of 1 <= loc <= (length of list)+1. Let us say the length of the list is 10 & the user want to insert at location 12 (sounds stupid).


• As we know we can traverse Bi-Directional in case of Doubly Linked Lists so we have to take care of PREV and NEXT variables in the NODE structure. We should also update the neighboring Nodes which are affected by this operation. If not we might break up the List somewhere or the other by creating a BROKEN LIST.

We have following scenarios in the case of insertion of a NODE.

• Adding a Node at the start of the Empty List



Figure 1: Empty List and the newNode we want to add

As shown in Figure-1 we have a Empty List with LENGTH set to 0 and FIRST pointing to NULL. Let us add newNode at Location 1. 

In HEAD - FIRST variable points to newNode (head->FIRST = newNode).

In newNode - NEXT and  PREV points to NULL as we don't have any other Nodes in the List.

Increment the LENGTH variable in HEAD once insertion is successful to maintain the count of number of Nodes in the List.

Pseudocode:

HEAD->FIRST = newNode

newNode->PREV = NULL

newNode->NEXT = NULL

increment(HEAD->LENGTH)

Output:

Figure 2: After adding newNode in Empty List. (Changes in BLUE)