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)

• Adding a Node at the start of the Non-Empty List



Figure 3: A Doubly Linked List of Length 3.

As shown in Figure-3 we have a list of length 3. Let us call current first Node as curFirstNode. 

In newNode - NEXT points to curFirstNode (newNode->NEXT = head->FIRST) and PREV points to NULL as the newNode itself is the first in the List.

In curFirstNode - PREV points to newNode (HEAD->FIRST->PREV = newNode) and NEXT remains unchanged. (we have to update curFirstNode before HEAD since it holds the pointer to curFirstNode)

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

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->NEXT = HEAD->FIRST

HEAD->FIRST->PREV = newNode

HEAD->FIRST = newNode

newNode->PREV = NULL

increment(HEAD->LENGTH)

Output:

Figure 4: After adding newNode at location 1. (Changes in BLUE)

• Adding a Node at the middle of the list. 
Now we will see how to add a newNode at the arbitrary location. 



Figure 5: Current Preview of the Doubly Linked List.

Let us add a newNode at Location 3. 

Traverse the Doubly Linked List until the Location 2. So our curPtr is pointing to Node 2.

In newNode - PREV points to NODE 2 (newNode->PREV = curPtr) and NEXT points to NODE 3 (newNode->NEXT = curPtr->NEXT).

In NODE3 - PREV points to newNode (newNode->NEXT->PREV = newNode) and NEXT remains unchanged.

In NODE2 - NEXT points to newNode (curPtr->NEXT = newNode) and PREV remains unchanged.

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->PREV = curPtr

newNode->NEXT = curPtr->NEXT

newNode->NEXT->PREV = newNode

curPtr->NEXT = newNode

increment(HEAD->LENGTH)

Output:

Figure 6: After adding newNode at Location 3 (Changes in BLUE)

• Adding a Node at the End of the List
Traverse until the end of the List so that the curPtr points to Last Node in the List.

In Last Node - NEXT points to newNode (curPtr->NEXT = newNode) and PREV remains unchanged.

In newNode - PREV points to Last Node (newNode->PREV = curPtr) and NEXT points to NULL since we are the last Node in the List.

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

curPtr->NEXT = newNode

newNode->PREV = curPtr

increment(HEAD->LENGTH)

Let us see the preview of the C code which does the insertion of a Node at a particular location.

This code is generic for all the possible scenarios explained above.

addNodeAtLoc(listHead *head, listNode *newNode, UINT32 loc)
{
    UINT32 i;
    retVal ret = SUCCESS;

    listNode *curPtr;

    if(head && newNode && loc && (loc <= (head->length)+1))
    {   
        if(loc == 1)
        {   
            newNode->prev = NULL;
            newNode->next = head->first;
    
            if(head->first)
                head->first->prev = newNode;

            head->first = newNode;
        }   
        else
        {   
            curPtr = head->first;

            for(i=1; i<(loc-1); i++)
                curPtr = curPtr->next;

            newNode->prev = curPtr;
            newNode->next = curPtr->next;

            if(curPtr->next)
                curPtr->next->prev = newNode;

            curPtr->next = newNode;
        } 

        head->length++;
    }
    else
        ret = FAILURE;

    return ret;
}

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