Inserting Node into a Sorted Doubly Linked List

Recently, I was solving some coding questions on Hackerrank and I came across this problem. I realised that this problem lacked explanation and the approach to solve it.

In this article, I will give you a brief about the problem and will also tell the approach to solve it.

The Explanation: We are given a Doubly Linked List which is already sorted, we need not write the code for sorted it. The first though that I had in my mind was that I need to sort the DLL and then I will insert the new node. Since the DLL is already sorted we now need to add the new node in a sorted manner.

Example: Let’s better understand the problem with an example. The format of the input is testcases, number of nodes, values of those nodes and then the value of the new node.

STDIN   Function
-----   --------
1       t = 1
4       n = 5
1       node data values = 1, 3, 4, 7, 9
3
4
7
9
5       data = 5

Represented in a diagrammatic manner:

As you can see, new node’s value, 5 is inserted in a sorted manner after 4 and before 7. It is similar to inserting a node in the middle but with a twist.

The Approach: We have to check for the rest of the values of the node, if they are greater than the new node’s value then it will be inserted before that node. We can traverse the list from left to right and find a suitable position for the new node to insert. It is useful to first examine the different positions that the new node could end up in, and then we can analyse each of those cases independently.

1. Empty list
2. At the beginning of the list
3. Somewhere at the middle of the list
4. At the end of the list

We’ll create a newNode and assign it the data value

DoublyLinkedListNode *newNode;
newNode -> data = data;

Empty List: newNode’s prev and next pointers will be set to NULL since it will be the only node in the list and then return the newNode.

if(head == NULL){
newNode -> prev = NULL;
newNode -> next = NULL;
return newNode;
}

Beginning of the list: Now, we will check if any of the node’s value is greater than equal to that of newNode’s value. If the newNode is to be inserted at the beginning, then its next pointer should point to the current head, the prev pointer to NULL. Also, the head’s prev pointer has to be updated to point to this node. Finally, the node has to be assigned as the new head of the list.

if(head->data >= newNode->data){
newNode -> next = head;
head -> prev = newNode;
newNode -> prev = NULL;
head = newNode;

Middle of the List: In this case, we will have to find two nodes in between which we can place this newNode. If we denote these as left and right respectively then,

left->data < newNode->data && right->data >= newNode->data

Here, it is useful to mention that we can actually get away by using only one extra node. We can denote “current” as the left node, and current->next as the right node. So we need to traverse the list from the head until we have current->next->data < newNode -> data. Obviously by doing this, we have already made sure that current -> data < newNode -> data.

current = head;
while(current->next != NULL && current->next->data < newNode->data) {
    current = current->next;
}

Now we have newNode in between current and current -> next . We have to set its next and prev pointers.

newNode->next = current->next;
newNode->prev = current;

Also we need to update the next pointer of current and prev pointer to current->next to point to this newNode.

current->next->prev = newNode;
 current->next = newNode;

Note that it is important to follow the sequence of update operations. For example if we swap the last two lines, we would get incorrect results.

current->next = newNode; //current->next now points to the newNode
    current->next->prev = newNode; //current->next is the newNode, so its prev (i.e. newNode->prev) is set back to newNode which is incorrect.

At the end of the list — Again we need to traverse till the end of the list and update the pointers. If you observe carefully, it is the same as the previous case, just we do not have current->next node in the list (it is NULL here). So we can reuse the same code again, but we cannot update the current -> next -> prev pointer (because current -> next is NULL here). Hence we can just add a condition in the previous code that if current -> next is NOT NULL then only update its prev pointer.

CODE IN C++:

DoublyLinkedListNode *newNode;
newNode->data = data;
if(head == NULL) {
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
if(head->data >= newNode->data) {
newNode->next = head;
newNode->prev = NULL;
head->prev = newNode;
head = newNode;
}
else {
DoublyLinkedListNode *current = head;
while(current->next != NULL && current->next->data < newNode->data) {
  current = current->next;
}
newNode->prev = current;
newNode->next = current->next;
if(current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
}
return head;