Sorted Insertion in a sorted Doubly Linked List

Introduction

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.

We can traverse the doubly linked list in the forward and backward directions because it has two pointers, prior and next. In this blog, we will discuss a famous problem of Doubly Linked List.

Problem Statement

Given a sorted Doubly Linked List in this problem, we must insert a value in the list at its correctly sorted position, ensuring that the resultant list is also sorted.

Example

1. Let us take the following doubly linked list as an example:

Let us assume we want to insert 8 in the given list.

Hence after insertion, the linked list should look like the following.

2. Let us take the following doubly linked list as an example:

Let us assume we want to insert 15 in the given list.

Hence after insertion, the linked list should look like the following.

Algorithm

• If the head is null. The list is empty.
   
• if head->data >= newNode.data, put the newNode at the start.
   
• Else,
  • Use the head node to initialize the pointer variable curr.
     
  • Using pointer curr, we'll begin traversing the linked list.
     
  • If the value of newNode which we have to insert is less than curr->next->data, we must insert the given node at the suitable point.
     
• Finally, print the Doubly Linked List that has been changed.

Implementation in Java

public class Main
{
// defining node
   public  static class ListNode {
       int data;
       ListNode prev,next;
       ListNode(){}
       ListNode(int data){
           this.data=data;
       }
       ListNode(int data, ListNode prev,ListNode next){
           this.data=data;
           this.prev=prev;
           this.next=next;
       }
   }
// function to add new node at the end 
   public static ListNode append(ListNode head, int x){
       ListNode newNode =new ListNode ();
       newNode.data=x;
       newNode.next=null;
       if(head==null){
           head=newNode;
           newNode.prev=null;
          return head;
       }
       ListNode temp=head;
       while(temp.next!=null){
           temp=temp.next;
       }
       temp.next=newNode;
       newNode.prev=temp;
       return head;
       
       
   }
//Function to insert node at a given position
   public static ListNode insert(ListNode head, int x){
       ListNode newNode = new ListNode();
       newNode.data=x;
       newNode.prev=null;
       newNode.next=null;
           ListNode temp;
       if(head==null){
           head=newNode;
           return head;
       }
   
    if (head.data >= x){
           newNode.next=head;
           newNode.next.prev=newNode;
           head=newNode;
           return head;
       }
       
       else{
            temp=head;
           while(temp.next!= null && temp.next.data < x)
           {
               temp=temp.next;
           }
           
           newNode.next=temp.next;
           if(temp.next!= null){
               newNode.next.prev=newNode;
           }
           
           temp.next=newNode;
           newNode.prev=temp;
           
           
       }
       return head;
           
       
   }
// function to display list
   public static void display(ListNode head){
       if(head==null){
           System.out.println("List is empty");
           return;
       }
       while(head!=null){
           System.out.print(head.data +" ");
           head=head.next;
       }
   }
// driver function
public static void main(String[] args) {
      ListNode head=null;
      head=append(head,10);
      head=append(head,20);
      head=append(head,40);
      System.out.println("List before insertion");
      display(head);
      System.out.println("\n");
    head=insert(head,30); //element to be inserted
      System.out.println("list after insertion");
      display(head);
  }
}

You can also try this code with Online Java Compiler

Run Code

Output

List before insertion
10 20 40 
List after insertion
10 20 30 40 

Complexity Analysis

Time Complexity 

Since we are linearly traversing the doubly linked list therefore the time complexity would be O(n), where n is the total number of nodes in the Doubly Linked List.

Space Complexity 

If we consider the space used to store the linked list, the space complexity is O(n), else we can say this approach has O(1) space complexity.

Also see,  Rabin Karp Algorithm