Introduction
The Doubly Linked List is a variant of the linked list. It is a collection of nodes that each include twopointers 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
 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.

Use the head node to initialize the pointer variable curr.
 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);
}
}
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