Sorted insertion in doubly linked list
This article focuses on the implementation of inserting nodes in sorted order into a doubly linked list. When inserting elements into a doubly linked list, maintaining the sorted order can be crucial in various scenarios. This article explains how to perform sorted insertion efficiently in a doubly linked list using Java code examples and step-by-step explanations.

Problem Statement
Given a doubly linked list and a new value, the task is to insert the new value into the list while maintaining the sorted order.
Example
Suppose we have the following sorted doubly linked list:
1 <-> 3 <-> 4 <-> 6 <-> 8 <-> 11 <-> 12
If we want to insert the value 5
, the resulting list should become:
1 <-> 3 <-> 4 <-> 5 <-> 6 <-> 8 <-> 11 <-> 12
Idea to Solve
The idea is to traverse the linked list and find the appropriate position to insert the new value while maintaining the sorted order.
Pseudocode
function insert(value):
create a new node with the given value
if head is null:
set head to the new node
else if head.data >= value:
insert new node at the beginning
else:
current = head
while current is not null and current.next is not null and current.next.data <= value:
move current to the next node
insert new node after current
update previous and next pointers accordingly
Algorithm Explanation
- Implement an
insert
function that takes thevalue
as a parameter. - Create a new node with the given
value
. - If the
head
isnull
, set thehead
to the new node. - If the
head.data
is greater than or equal to thevalue
, insert the new node at the beginning of the list. - Otherwise, initialize
current
withhead
and traverse the list to find the correct position to insert the new node. - After finding the correct position, insert the new node after
current
. - Update the
prev
andnext
pointers of the nodes accordingly to maintain the doubly linked structure.
Code Solution
-
1) Sorted order insertion in doubly linked list in java
2) Sorted order insertion in doubly linked list in c
3) Sorted order insertion in doubly linked list in c++
4) Sorted order insertion in doubly linked list in golang
5) Sorted order insertion in doubly linked list in c#
6) Sorted order insertion in doubly linked list in php
7) Sorted order insertion in doubly linked list in python
8) Sorted order insertion in doubly linked list in ruby
9) Sorted order insertion in doubly linked list in scala
10) Sorted order insertion in doubly linked list in swift
11) Sorted order insertion in doubly linked list in kotlin
12) Sorted order insertion in doubly linked list in vb.net
13) Sorted order insertion in doubly linked list in node js
14) Sorted order insertion in doubly linked list in typescript
Time Complexity
The time complexity of sorted insertion in a doubly linked list is O(n), where n is the number of nodes in the list. This is because in the worst case, we might need to traverse the entire list to find the correct position for insertion.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment