Posted on by Kalkicode
Code Doubly linked list

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.

insert sorted doubly linked list

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

  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.

Code Solution

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.

New Comment