Posted on by Kalkicode

# Insert a node in sorted linked list

The problem at hand is about inserting a new node into a singly linked list while keeping the list sorted in ascending order. In a singly linked list, each element (node) holds a value and a reference to the next element in the list. The goal is to design a program that can efficiently insert a new node with a given value into the appropriate position in the sorted linked list.

## Problem Statement and Description

Given a sorted singly linked list, the task is to insert a new node with a given value while maintaining the sorted order of the list. This means that the new node should be inserted at a position where it fits between the nodes with values that are smaller and larger than its value. The ultimate objective is to have a sorted linked list after the new node is inserted.

## Example

Let's take a simple example to understand the problem better. Consider the following sorted linked list:

Original sorted linked list: -1 → 1 → 5 → 6 → 8 → 13 → NULL

We want to insert three new nodes: -5, 15, and 7.

After inserting -5: -5 → -1 → 1 → 5 → 6 → 8 → 13 → NULL

After inserting 15: -5 → -1 → 1 → 5 → 6 → 8 → 13 → 15 → NULL

After inserting 7: -5 → -1 → 1 → 5 → 6 → 7 → 8 → 13 → 15 → NULL

## Idea to Solve the Problem

To solve this problem, we need to identify the appropriate position to insert the new node while maintaining the sorted order. There are a few key scenarios to consider:

1. Insertion at the Beginning

If the new value is smaller than or equal to the value of the first node, the new node becomes the new head of the linked list.

2. Insertion at the End

If the new value is greater than or equal to the value of the last node, the new node becomes the new tail of the linked list.

3. Insertion in the Middle

If the new value is somewhere between the values of existing nodes, we need to find the right position to insert the new node. This involves traversing the linked list and finding the node after which the new node should be inserted.

## Standard Pseudocode

``````sortedAdd(data):
newNode = new Node(data)

else if data >= tail.data:
tail.next = newNode
tail = newNode
else:
while current.next is not null and current.next.data < data:
current = current.next
newNode.next = current.next
current.next = newNode``````

## Algorithm Explanation

1. Create a new node (`newNode`) with the given data.
2. If the linked list is empty or the new data is smaller than the value of the current head, insert the new node at the beginning. Update the `head` accordingly.
3. If the new data is greater than the value of the current tail, insert the new node at the end. Update the `next` of the current tail and update the `tail` to the new node.
4. If the new data falls between existing nodes, traverse the linked list (`current` starts from `head`) while the value of `current.next` is less than the new data. This helps to find the correct position to insert the new node.
5. Once the correct position is found (where `current.next.data >= data`), adjust the pointers to insert the new node. Set `newNode.next` to `current.next` and update `current.next` to `newNode`.

## Time Complexity Analysis

• In the best case, when inserting at the beginning or end, the insertion operation takes constant time, O(1).
• In the worst case, when inserting in the middle, the algorithm needs to traverse the entire linked list, taking linear time in the number of nodes, O(n).
• Overall, the time complexity of inserting a node in a sorted linked list using this algorithm is O(n), where n is the number of nodes in the linked list.

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