Insert value in sorted way of doubly linked list
The problem at hand revolves around inserting values into a doubly linked list in a sorted order. A doubly linked list is a linear data structure in which elements are stored as nodes. Each node has a value (data), a reference to the next node (next), and a reference to the previous node (prev). Sorting means arranging elements in a specific order, such as ascending or descending, based on their values.

Problem Statement
We are given a doubly linked list and want to insert new values into it while maintaining the sorted order. The sorted order implies that the values in the list should be arranged in ascending order from the head to the tail.
Example
Let's consider an example to illustrate the problem. Suppose we have an initially empty doubly linked list. We want to insert the values 5, 3, 11, 4, 6, 1, 8, and 12 into the list. After inserting these values, the doubly linked list should look like this:
Linked List Head to Tail: 1 3 4 5 6 8 11 12 Linked List Tail to Head: 12 11 8 6 5 4 3 1
Idea to Solve
To solve this problem, we need to traverse the existing sorted doubly linked list and find the appropriate position to insert the new value while maintaining the sorted order. We can start at the head of the list and compare the value of the current node with the value to be inserted. We continue moving forward until we find the correct position for insertion.
Pseudocode
Here's the pseudocode that outlines the algorithm to insert a value into a sorted doubly linked list:
function insert(sortedList, value):
node = createNode(value)
if sortedList.head is null:
sortedList.head = node
else if sortedList.head.data >= node.data:
node.next = sortedList.head
sortedList.head.prev = node
sortedList.head = node
else:
current = sortedList.head
while current is not null and current.next is not null and current.next.data <= value:
current = current.next
node.next = current.next
if current.next is not null:
current.next.prev = node
node.prev = current
current.next = node
Algorithm Explanation
- We start by creating a new node with the value to be inserted.
- If the sorted list is empty (head is null), we simply assign the new node as the head.
- If the head of the list has a value greater than or equal to the value of the new node, we insert the new node at the beginning of the list.
- Otherwise, we traverse the list using the
current
pointer until we find a node with a value greater than the value of the new node or until we reach the end of the list. - We then adjust the pointers of the neighboring nodes to insert the new node in its appropriate position.
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
Resultant Output Explanation
After inserting the given values into the doubly linked list using the described algorithm, the list becomes: 1 3 4 5 6 8 11 12. The head-to-tail and tail-to-head traversal outputs are as mentioned in the example output.
Time Complexity
- In the worst case, when the value needs to be inserted at the end of the list, the algorithm performs a linear traversal of the list.
- The worst-case time complexity of the insertion algorithm is O(n), where n is the number of nodes in the linked list.
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