Last Updated on November 25, 2022 by Prepbytes
In this article , will learn how to write a program to insert a new node into a sorted linked list without disturbing the order.As we know in linked list is a sequence of data structures that are connected through links and each node contains the address of the next node.Now let’s try to understand to insert a new node into a sorted linked list without disturbing the order.
How to insert a new node into a sorted linked list without disturbing the order.
In this question, we are given a singly linked list. We are also given an element that is to be inserted into the list. But, the given list is sorted. So, the insertion should be done in such a way that the sorted order of the linked list is not disturbed.
Suppose the given linked list is 1 -> 5 -> 9 -> 11 -> 20, and the element to be inserted is 15.
So, according to the problem, 15 should be inserted between 11 and 20, as we also have to maintain the sorted order of the list.
So, the final list is 1 -> 5 -> 9 -> 11 -> 15 -> 20.
Input:
Element to be inserted – 15.
Output:
Explanation: As the given list is sorted in ascending order, we have inserted 15 in an appropriate position, which maintains the sorted order of the list.
As we know, insertion and deletion in a singly linked list are very efficient, but list traversal takes O(n) time. We are going to use the list traversal, but with a few tweaks. Let us have a glance at the approach.
Approach to insert a new node into a sorted linked list without disturbing the order.
The approach is going to be pretty simple. We know the given linked list is already sorted. So, to insert a new element in a sorted way, we have to find an appropriate position for the new element, such that the order is not disturbed.
We are going to traverse through the list and look for the appropriate position to insert the element. To find the position, we are going to run the loop till will find a node, say, temp, whose value is greater than the new node. The node just before temp is the appropriate node.
In the end, we are going to insert the new node just after the appropriate node.
Algorithm to insert a new node into a sorted linked list without disturbing the order.
- Base Case 1 – If the list is empty, then make the new node as head.
- Base Case 2 – If the new node value is lesser than the head node, then insert it at the start, make it the head.
- Traverse through the list until the data of the next of current is less than the data of the new node. By doing this, we are looking for an appropriate position to insert the new node.
- When the loop breaks, insert the new node just after the current node:
1) New_node – > next = current – > next
2) current – > next = New_node
Dry Run to insert a new node into a sorted linked list without disturbing the order.
Code Implementation to insert a new node into a sorted linked list without disturbing the order.
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
void sortedInsert(struct Node** head_ref,
struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
current = *head_ref;
while (current->next != NULL
&& current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
struct Node* newNode(int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf("\n Created Linked List\n");
printList(head);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
class Node {
public:
int data;
Node* next;
};
void sortedInsert(Node** head_ref,
Node* new_node)
{
Node* current;
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
current = *head_ref;
while (current->next != NULL
&& current->next->data
< new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Node* newNode(int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
void printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
int main()
{
Node* head = NULL;
Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(11);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
new_node = newNode(20);
sortedInsert(&head, new_node);
new_node = newNode(15);
sortedInsert(&head, new_node);
cout << "Created Linked List\n";
printList(head);
return 0;
}
public class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void sortedInsert(Node new_node)
{
Node current;
if (head == null || head.data
>= new_node.data) {
new_node.next = head;
head = new_node;
}
else {
current = head;
while (current.next != null
&& current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
Node newNode(int data)
{
Node x = new Node(data);
return x;
}
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
new_node = llist.newNode(11);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(20);
llist.sortedInsert(new_node);
new_node = llist.newNode(15);
llist.sortedInsert(new_node);
System.out.println("Created Linked List");
llist.printList();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def sortedInsert(self, new_node):
if self.head is None:
new_node.next = self.head
self.head = new_node
elif self.head.data >= new_node.data:
new_node.next = self.head
self.head = new_node
else :
current = self.head
while(current.next is not None and
current.next.data < new_node.data):
current = current.next
new_node.next = current.next
current.next = new_node
def printList(self):
temp = self.head
while(temp):
print(temp.data, end = " ")
temp = temp.next
llist = LinkedList()
new_node = Node(5)
llist.sortedInsert(new_node)
new_node = Node(1)
llist.sortedInsert(new_node)
new_node = Node(11)
llist.sortedInsert(new_node)
new_node = Node(9)
llist.sortedInsert(new_node)
new_node = Node(20)
llist.sortedInsert(new_node)
new_node = Node(15)
llist.sortedInsert(new_node)
print("Create Linked List", end=" ")
llist.printList()
Output
Created Linked List: 1 5 9 11 15 20Space Complexity: O(1), as only temporary variables are being created.
So, in this article, we have explained to insert a new node into a sorted linked list without disturbing the order.In this question we have seen how we have inserted a element in sorted linked list without disturbing order in efficient way as insertion and deletion is one of the key operations used in linked list.If you see there are many applications of sorted insertion in linked list problems.If you want to solve more questions on Linked List, you can follow this link Linked List.
FAQs to insert a new node into a sorted linked list without disturbing the order.
1. How many references must have to change to insert a node in the middle of a singly linked list?
Basically two pointers are needed to be modified for insertion in the middle of a linked list, the node before the node to be inserted and the node which is being inserted.
2. What is the time complexity of insertion operation at middle of linked list?
Each insert operation should take O(1) time complexity.
3. How many passes does an insertion sort consists of?
An insertion algorithm consists of N-1 passes when an array of N elements is provided.