Part 12 of 26 in Linked List - set 02

Problem statement

Create a doubly link list of integers by inserting the nodes in sorted order.

Input

You must write a function with signature "Node* SortedInsert(Node* head, int data)" that will take as argument pointer to the head of a doubly linked list and integer to be inserted.

Output

The function must return address of the head node after insertion. The data in nodes must be in sorted order after each insertion. Also, both next and prev links for all nodes must be correct.

Problem description
We are given a node and a sorted doubly linked list. The problem asks us to insert this node into the list, such that the list remains sorted.

Solution
The first thing to observe is that the doubly linked list given is sorted at all times, i.e. `Li <= Lj` for all `i < j`. Therefore 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.

• Empty list
• At the beginning of the list
• Somewhere at the middle of the list
• At the end of the list
In any of the four cases, we need to allocate memory for our new node and also assign its data. So we can do this common operation first.
```Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
```
Having done this, we now need to set this newNode's next and prev pointers and possibly update some other node's pointers to adjust this node's position in the list. Now we will examine each of the cases separately.

Empty list - This is the trivial base case in which the list given is empty, and it is the first element to be inserted. So we can simply put its next and prev pointers to NULL and return this node as the head of the list.

At the beginning of the list - 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.

Somewhere in the 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.

editorial written by phantom11

```/*
Insert Node in a doubly sorted linked list
After each insertion, the list should be sorted
Node is defined as
struct Node
{
int data;
Node *next;
Node *prev
}
*/
{
//reserve memory for this new node
Node *newNode = (Node*) malloc(sizeof(Node));
//Set the data of newNode as data
newNode->data = data;
//Now we need to update the next and prev pointers of newNode -
//based on its position
//Base case : If the list is empty
newNode->next = NULL; //Set next and prev pointers as NULL
newNode->prev = NULL;
//This node now becomes the head node(the only node), so return it.
return newNode;
}
//If the node's position is in the beginning of the list
//set the next pointer of the newNode to point to the currentHead
newNode->prev = NULL; //Because it is the beginning of the list
//Update the prev pointer of the current head to point to newNode
//This node now becomes the head node, so make it.
} else {
//Find the position of the new node using a temporary current Node
while(current->next != NULL && current->next->data < newNode->data) {
current = current->next;
}
//newNode lies between current and current->next
newNode->prev = current;
newNode->next = current->next;
//It might happen that newNode's position is at the end.
//In that case we cannot update the current->next's (which is NULL)
//prev pointer
if(current->next != NULL) {
current->next->prev = newNode;
}
//Update the next pointer of current to point to this new node.
current->next = newNode;
}