Posted on by Kalkicode

# Sorted order insertion of linked list

The problem discussed in this context involves adding nodes to a singly linked list in a sorted order. A singly linked list is a linear data structure where each element, known as a node, is composed of two parts: data and a reference to the next node. The goal is to design a program that can insert new nodes into the linked list while maintaining the sorted order of the elements. ## Problem Statement and Description

Given a singly linked list, the task is to insert a new node with a given value in such a way that the overall structure remains sorted. This means the new node should be placed in a position that preserves the ascending order of values within the list.

## Example

Consider the scenario where you have the following numbers: 1, -3, 9, 4, 11, and -7. You want to create a sorted linked list from these numbers. The expected sorted linked list should look like this: -7 → -3 → 1 → 4 → 9 → 11 → NULL.

## Idea to Solve the Problem

To solve this problem, we need to maintain the sorted order of the linked list while adding new nodes. The algorithm needs to consider different scenarios:

1. Insertion at the Beginning

If the new value is smaller than the value of the current head node, the new node becomes the new head.

2. Insertion in the Middle

Traverse the linked list while comparing the new value with the values of the existing nodes. Insert the new node in a position that maintains the sorted order.

3. Insertion at the End

If the new value is greater than the value of the current tail node, the new node becomes the new tail.

## Standard Pseudocode

``````sortedAdd(sll, data):
newNode = createNewNode(data)

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 or equal to the value of the current head, insert the new node at the beginning. Update `newNode.next` to point to the current head and update the head to `newNode`.
3. If the new data is greater than the value of the current head, traverse the linked list (`current` starts from `sll.head`). Find the correct position to insert the new node. This is done by comparing `data` with `current.next.data` in each iteration.
4. 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, the insertion operation takes constant time, O(1).
• In the worst case, when inserting at the end or 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