Insert a value in a sorted way in a sorted Doubly Linked List

Introduction

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.

Problem Statement

In this problem, we are given a sorted Doubly Linked List and we need to insert a value in the list at its correct sorted position.

Problem Statement Understanding

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, 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

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

  • If the head is null, that means 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 it 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


Code Implementation:

#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: O(n), where n is the total number of nodes in the Doubly Linked List and traversal requires an O(n) time complexity.

So, in this blog, we have tried to explain how you can insert a value in a sorted way in a sorted doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Implement a stack using a singly linked list
Next post Search an element in a Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *