Insert a Value in a Sorted Way in a Sorted Doubly Linked List

Last Updated on November 10, 2022 by Sumit Kumar

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview. A doubly Linked List is a type of linked list which has a node consisting of one storage of data and two pointers (one is the next pointer which will have the address of the next node and one is the prev pointer which will have the address of the previous node). In this article, we will discuss how to insert a node into a sorted doubly linked list

How to Insert a Node Into a Sorted Doubly Linked List

In this problem, we are given a sorted Doubly Linked List and we need to insert a node into a sorted doubly linked list.

According to the problem statement, we need to insert a node with a value X in the sorted Doubly Linked List such that the resultant list after insertion is also sorted.

Let’s try to understand the problem statement with the help of examples.

If the given Sorted doubly linked list is:

X = 8

• We can see that 8 is greater than 4, 5, 7, and smaller than 9, 12, 17, and 19, so we will insert 8 after 7 and before 9 in the given linked list.
• The output Linked list after inserting 8 will be :

If the given list is: head -> 1 4 9 11 13 22 and X = 3.

• In this case after inserting the node with value X = 3 at its correct position in linked list our output linked list will be : head -> 1 3 4 9 11 13 22.

Some more examples

• Sample Input 1: head -> 2 4 6 8 10, X = 5
• Sample Output 1: head -> 2 4 5 6 8 10
  
• Sample Input 2: head -> 1 3 5 9 11 13, X = 7
• Sample Output 2: head -> 1 3 5 7 9 11 13

Now I think from the above example, the problem statement is clear. So let’s see how we will approach it.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move to the approach section.

Approach For Inserting A Node Into A Sorted Doubly Linked List

The approach will be simple:

• In order to insert a node with value X in a sorted list in sorted order, we need to traverse the list till the data of the next node of current is smaller than the given value X.
• After reaching the correct position, we will simply insert a new node with value X over there.
• This method is the same for both singly and doubly list. The only difference is that in Doubly Linked List, we have to take care of the prev pointer along with the next pointer.

Algorithm For Inserting A Node Into A Sorted Doubly Linked List

• If the head is null, the list is empty. newNode (Node with value X, which we want to insert in the list) is the only node in the list. Make its head and return head.
• Else if head->data >= newNode.data, that means the newNode needs to be inserted at the beginning.
• Else:
  • Initialize pointer variable current with head node.
  • We will start traversing the linked list using pointer current.
  • While traversing, if we encounter current->next->data greater than the X, i.e., the value of newNode which we have to insert is smaller than current->next->data, then we need to insert the given node at that position by following below steps:
    • Make next of newNode (node that needs to be inserted) equal to next of current node (newNode->next = current.next).
    • If next of current is not null, i.e., newNode not inserted at end, make newNode->next->prev = newNode.
    • Make next of current node as newNode (current->next = newNode).
    • Make Prev of the newNode as current (newNode->prev = current).
• Finally, output the updated Doubly Linked List.

Dry Run For Inserting A Node Into A Sorted Doubly Linked List

Code Implementation For Inserting A Node Into A Sorted Doubly Linked List:

#include 
using namespace std;

/* Node structure of our doubly linked list */
struct DLLNode {
    int data;
    struct DLLNode* prev, *next;
};

/* Using this function we will be creating and returning a new node of doubly linked list */
struct DLLNode* CreateNewNode(int data)
{
    struct DLLNode* newNode = (struct DLLNode*)malloc(sizeof(struct DLLNode));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

/* This is the function using which we will be inserting a new node in a sorted doubly linked list in sorted way */
void InsertionSortedManner(struct DLLNode** head, struct DLLNode* newNode)
{
    struct DLLNode* current;
    
    if (*head == NULL){
        *head = newNode;
    }
    
    else if ((*head)->data >= newNode->data) {
        newNode->next = *head;
        newNode->next->prev = newNode;
        *head = newNode;
	}
    
    else {
        current = *head;
        while (current->next != NULL && current->next->data < newNode->data){
            current = current->next;
        }
        
        newNode->next = current->next;
        
        if (current->next != NULL){
            newNode->next->prev = newNode;
        }
       
       current->next = newNode;
       newNode->prev = current;
    }
}

/* Using this function we will be printing the doubly linked list */
void printList(struct DLLNode* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

int main()
{
    struct DLLNode* head = NULL;
    struct DLLNode* new_node = CreateNewNode(8);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(5);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(4);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(7);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(9);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(19);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(12);
    InsertionSortedManner(&head, new_node);
    new_node = CreateNewNode(17);
    InsertionSortedManner(&head, new_node);

    cout << "Doubly Linked List before insertion "<

						 

Output

Doubly Linked List before insertion
4 5 7 8 9 12 17 19
Doubly Linked List after insertion of node with value 15
4 5 7 8 9 12 15 17 19

Time Complexity For Inserting A Node Into A Sorted Doubly Linked List: O(n), where n is the total number of nodes in the Doubly Linked List and traversal requires an O(n) time complexity.

With the help of this blog, we have explained to you how to insert a node into a sorted doubly linked list. A doubly linked list is one of the most important data structures for cracking interviews. If you want to solve more questions on Linked List, which our expert mentors at PrepBytes curate, you can follow this link Linked List.

FAQ Related To Inserting A Node Into A Sorted Doubly Linked List

1. What is a sorted doubly linked list?

The doubly linked list is a variant of the linked list. It is a collection of nodes that each include two-pointers and each node carries a value which is also known as data. The first pointer points to the node before it, while the second pointer points to the node after it.

2. Which is the node structure of a doubly linked list?

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.

3. How do you traverse a doubly linked list?

Traversing is the most common operation in the case of each data structure. For this purpose, copy the head pointer in any of the temporary pointer ptr. then, traverse through the list by using a while loop.

4. Why is a doubly linked list called Two Way list?

A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.