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:
-
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.
-
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.
-
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)
if head is null or data <= head.data:
newNode.next = head
head = newNode
else if data >= tail.data:
tail.next = newNode
tail = newNode
else:
current = 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 the value of the current head, insert the new node
at the beginning. Update the
head
accordingly. - 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 thetail
to the new node. - If the new data falls between existing nodes, traverse the linked list (
current
starts fromhead
) while the value ofcurrent.next
is less than the new data. This helps to find the correct position to insert the new node. - 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) Insert an element in a sorted linked list in java
2) Insert an element in a sorted linked list in c++
3) Insert an element in a sorted linked list in c
4) Insert an element in a sorted linked list in c#
5) Insert an element in a sorted linked list in vb.net
6) Insert an element in a sorted linked list in php
7) Insert an element in a sorted linked list in typescript
8) Insert an element in a sorted linked list in python
9) Insert an element in a sorted linked list in ruby
10) Insert an element in a sorted linked list in scala
11) Insert an element in a sorted linked list in swift
12) Insert an element in a sorted linked list in kotlin
13) Insert an element in a sorted linked list in golang
14) Insert an element in a sorted linked list in node js
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.
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