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:

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.

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.

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)
if sll.head is null or data <= sll.head.data:
newNode.next = sll.head
sll.head = newNode
else:
current = sll.head
while current.next is not null and current.next.data < data:
current = current.next
newNode.next = current.next
current.next = newNode
Algorithm Explanation
 Create a new node (
newNode
) with the given data.  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 tonewNode
.  If the new data is greater than the value of the current head, traverse the linked list (
current
starts fromsll.head
). Find the correct position to insert the new node. This is done by comparingdata
withcurrent.next.data
in each iteration.  Once the correct position is found (where
current.next.data >= data
), adjust the pointers to insert the new node. SetnewNode.next
tocurrent.next
and updatecurrent.next
tonewNode
.
Code Solution

1) Sorted order insertion of linked list in c
2) Sorted order insertion of linked list in c++
3) Sorted order insertion of linked list in c#
4) Sorted order insertion of linked list in java
5) Sorted order insertion of linked list in php
6) Sorted order insertion of linked list in kotlin
7) Sorted order insertion of linked list in python 3
8) Sorted order insertion of linked list in ruby
9) Sorted order insertion of linked list in node js
10) Sorted order insertion of linked list in swift
11) Sorted order insertion of linked list in scala
12) Sorted order insertion of linked list in go
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.
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