1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Algorithm
2.1.
Implementation in Java
2.1.1.
Complexity Analysis
3.
3.1.
Is a doubly linked list contiguous?
3.2.
What are real-life applications of a doubly linked list?
3.3.
3.4.
Is removing a node faster in a doubly-linked list than a singly linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Sorted Insertion in a sorted Doubly Linked List

Prerna Tiwari
0 upvote

## 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;
newNode.prev=null;
}
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
newNode.prev=temp;

}
//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;
}

newNode.next.prev=newNode;
}

else{
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;

}

}
// function to display list
System.out.println("List is empty");
return;
}
}
}
// driver function
public static void main(String[] args) {
System.out.println("List before insertion");
System.out.println("\n");
System.out.println("list after insertion");
}
}``````

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

### Is a doubly linked list contiguous?

The LinkedList data structure is a linear data structure in which each element is an object. LinkedList, unlike Array, does not have a contiguous memory structure. A pointer connects each element to the next.

### What are real-life applications of a doubly linked list?

A back and forward button is used by the browser to implement backward and forward navigation of visited web pages. Various applications also use it to implement undo and redo functionality.

It consumes more memory than an array or a singly linked list. Because memory elements are stored randomly, they must be accessed sequentially; no direct access is permitted.

### Is removing a node faster in a doubly-linked list than a singly linked list?

If the cell to be removed is known ahead of time, the doubly-linked list allows us to do so in time O(1), whereas a singly-linked list would take time O(2) (n). If we don't know the cell ahead of time, the answer is O(n) in both cases.

## Conclusion

In this blog, we learned how to insert a value in the list at its correctly sorted position, ensuring that the resultant list is also sorted. We started with introducing the doubly linked list, problem statement, example, and implementation, and finally concluded with time complexity.

Recommended Problems -

We hope that after reading this blog you must have learned how we can insert a node in a Sorted Doubly linked list and now it is your turn to code this problem in your own way. If you want to learn more about Doubly Linked List then check out this link.

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!