Posted on by Kalkicode

# 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
set head to the new node
insert new node at the beginning
else:
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

1. Implement an `insert` function that takes the `value` as a parameter.
2. Create a new node with the given `value`.
3. If the `head` is `null`, set the `head` to the new node.
4. If the `head.data` is greater than or equal to the `value`, insert the new node at the beginning of the list.
5. Otherwise, initialize `current` with `head` and traverse the list to find the correct position to insert the new node.
6. After finding the correct position, insert the new node after `current`.
7. Update the `prev` and `next` pointers of the nodes accordingly to maintain the doubly linked structure.

## 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.

## Comment

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.

Categories
Relative Post