Given a sorted linked list and a value to insert, write a function to insert the value in a sorted way.
Initial Linked List
Linked List after insertion of 9
Algorithm:
Let input linked list is sorted in increasing order.
1) If Linked list is empty then make the node as head and return it. 2) If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head. 3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node GN (10 in the below diagram) who's value is greater than the input node. The node just before GN is the appropriate node (7). 4) Insert the node (9) after the appropriate node (7) found in step 3.
Implementation:
C++
/* Program to insert in a sorted list */#include <bits/stdc++.h>using namespace std;/* Link list node */class Node {public: int data; Node* next;};/* function to insert a new_node in a list. Note that this function expects a pointer to head_ref as this can modify the head of the input linked list (similar to push())*/void sortedInsert(Node** head_ref, Node* new_node){ 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 { /* Locate the node before the point of insertion */ 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; }}/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert *//* A utility function to create a new node */Node* newNode(int new_data){ /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; new_node->next = NULL; return new_node;}/* Function to print linked list */void printList(Node* head){ Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; }}/* Driver program to test count function*/int main(){ /* Start with the empty list */ Node* head = NULL; 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); cout << "Created Linked List\n"; printList(head); return 0;}// This is code is contributed by rathbhupendra |
C
/* Program to insert in a sorted list */#include <stdio.h>#include <stdlib.h>/* Link list node */struct Node { int data; struct Node* next;};/* function to insert a new_node in a list. Note that this function expects a pointer to head_ref as this can modify the head of the input linked list (similar to push())*/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 { /* Locate the node before the point of insertion */ 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; }}/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert *//* A utility function to create a 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;} |
Java
// Java Program to insert in a sorted listclass LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* function to insert a new_node in a list. */ void sortedInsert(Node new_node) { Node current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null&& current.next.data < new_node.data) { current = current.next; } new_node.next = current.next; current.next = new_node; } } /*Utility functions*/ /* Function to create a node */ Node newNode(int data) { Node x = new Node(data); return x; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } /* Driver function to test above methods */ 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(10); llist.sortedInsert(new_node); new_node = llist.newNode(7); llist.sortedInsert(new_node); new_node = llist.newNode(3); llist.sortedInsert(new_node); new_node = llist.newNode(1); llist.sortedInsert(new_node); new_node = llist.newNode(9); llist.sortedInsert(new_node); System.out.println("Created Linked List"); llist.printList(); }}/* This code is contributed by Rajat Mishra */ |
Python
# Python program to insert in a sorted list# Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = Noneclass LinkedList: # Function to initialize head def __init__(self): self.head = None def sortedInsert(self, new_node): # Special case for the empty linked list if self.head is None: new_node.next = self.head self.head = new_node # Special case for head at end elif self.head.data >= new_node.data: new_node.next = self.head self.head = new_node else : # Locate the node before the point of insertion 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 # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print it the LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next# Driver programllist = LinkedList()new_node = Node(5)llist.sortedInsert(new_node)new_node = Node(10)llist.sortedInsert(new_node)new_node = Node(7)llist.sortedInsert(new_node)new_node = Node(3)llist.sortedInsert(new_node)new_node = Node(1)llist.sortedInsert(new_node)new_node = Node(9)llist.sortedInsert(new_node)print "Create Linked List"llist.printList()# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# Program to insert in a sorted listusing System;public class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* function to insert a new_node in a list. */ void sortedInsert(Node new_node) { Node current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } } /*Utility functions*/ /* Function to create a node */ Node newNode(int data) { Node x = new Node(data); return x; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } } /* Driver code */ 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(10); llist.sortedInsert(new_node); new_node = llist.newNode(7); llist.sortedInsert(new_node); new_node = llist.newNode(3); llist.sortedInsert(new_node); new_node = llist.newNode(1); llist.sortedInsert(new_node); new_node = llist.newNode(9); llist.sortedInsert(new_node); Console.WriteLine("Created Linked List"); llist.printList(); }}/* This code is contributed by 29AjayKumar */ |
Javascript
<script>// javascript Program to insert in a sorted listvar head; // head of list /* Linked list Node */ class Node { constructor(val) { this.data = val; this.next = null; } } /* * function to insert a new_node in a list. */ function sortedInsert( new_node) { var current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } } /* Utility functions */ /* Function to create a node */ function newNode(data) { x = new Node(data); return x; } /* Function to print linked list */ function printList() { temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } /* Driver function to test above methods */ var new_node; new_node = newNode(5); sortedInsert(new_node); new_node = newNode(10); sortedInsert(new_node); new_node = newNode(7); sortedInsert(new_node); new_node = newNode(3); sortedInsert(new_node); new_node = newNode(1); sortedInsert(new_node); new_node = newNode(9); sortedInsert(new_node); document.write("Created Linked List<br/>"); printList();// This code is contributed by aashish1995</script> |
Output
Created Linked List 1 3 5 7 9 10
Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the list is needed. - Auxiliary Space: O(1).
No extra space is needed.
Shorter Implementation using double pointers:
Thanks to Murat M Ozturk for providing this solution. Please see Murat M Ozturk’s comment below for complete function. The code uses double-pointer to keep track of the next pointer of the previous node (after which new node is being inserted).
Note that below line in code changes current to have address of next pointer in a node.
current = &((*current)->next);
Also, note below comments.
/* Copies the value-at-address current to
new_node's next pointer*/
new_node->next = *current;
/* Fix next pointer of the node (using its address)
after which new_node is being inserted */
*current = new_node;
Time Complexity: O(n)
Auxiliary Space: O(1) because it is using constant space
Approach:
- If the linked list is empty, then make the new node as the head and return.
- Traverse the linked list till either current node becomes None or current node’s value is greater than the new node’s value.
- If the new node is to be inserted at the beginning, then the head of the linked list needs to be changed to the new node.
- If the new node is to be inserted at any other position, then the previous node’s next should point to the new node, and the new node’s next should point to the current node.
- Return the head of the linked list.
Code for another approach:
C++
#include <iostream>using namespace std;class Node {public: int data; Node* next; Node(int data) { this->data = data; next = nullptr; }};class LinkedList {private: Node* head;public: LinkedList() { head = nullptr; } void sortedInsert(Node* new_node) { if (head == nullptr) { head = new_node; return; } Node* prev = nullptr; Node* current = head; while (current && current->data < new_node->data) { prev = current; current = current->next; } if (prev == nullptr) { new_node->next = head; head = new_node; } else { new_node->next = current; prev->next = new_node; } } void push(int data) { Node* new_node = new Node(data); new_node->next = head; head = new_node; } void printList() { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } }};int main() { LinkedList llist; Node* new_node = new Node(5); llist.sortedInsert(new_node); new_node = new Node(10); llist.sortedInsert(new_node); new_node = new Node(7); llist.sortedInsert(new_node); new_node = new Node(3); llist.sortedInsert(new_node); new_node = new Node(1); llist.sortedInsert(new_node); new_node = new Node(9); llist.sortedInsert(new_node); cout << "Create Linked List" << endl; llist.printList(); return 0;} |
Java
class Node { int data; Node next; Node(int data) { this.data = data; next = null; }}public class LinkedList { Node head; // head of the list static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to insert a new node in a sorted way public void sortedInsert(Node new_node) { if (head == null) { head = new_node; return; } Node current = head; Node prev = null; while (current != null && current.data < new_node.data) { prev = current; current = current.next; } if (prev == null) { new_node.next = head; head = new_node; } else { new_node.next = current; prev.next = new_node; } } // Function to print the linked list public void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } } // Driver code public static void main(String[] args) { LinkedList list = new LinkedList(); Node new_node = new Node(5); list.sortedInsert(new_node); new_node = new Node(10); list.sortedInsert(new_node); new_node = new Node(7); list.sortedInsert(new_node); new_node = new Node(3); list.sortedInsert(new_node); new_node = new Node(1); list.sortedInsert(new_node); new_node = new Node(9); list.sortedInsert(new_node); System.out.println("Created Linked List"); list.printList(); }} |
Python3
# Node classclass Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node in a sorted way def sortedInsert(self, new_node): if self.head is None: self.head = new_node return prev = None current = self.head while current and current.data < new_node.data: prev = current current = current.next if prev is None: new_node.next = self.head self.head = new_node else: new_node.next = current prev.next = new_node # Utility function to print the LinkedList def printList(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next# Driver programllist = LinkedList()new_node = Node(5)llist.sortedInsert(new_node)new_node = Node(10)llist.sortedInsert(new_node)new_node = Node(7)llist.sortedInsert(new_node)new_node = Node(3)llist.sortedInsert(new_node)new_node = Node(1)llist.sortedInsert(new_node)new_node = Node(9)llist.sortedInsert(new_node)print("Create Linked List")llist.printList() |
C#
using System;public class Node{ public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}public class LinkedList{ public Node head; public LinkedList() { this.head = null; } public void SortedInsert(Node newNode) { if (this.head == null) { this.head = newNode; return; } Node prev = null; Node current = this.head; while (current != null && current.data < newNode.data) { prev = current; current = current.next; } if (prev == null) { newNode.next = this.head; this.head = newNode; } else { newNode.next = current; prev.next = newNode; } } public void PrintList() { Node temp = this.head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); }}public class Program{ public static void Main() { LinkedList llist = new LinkedList(); Node newNode = new Node(5); llist.SortedInsert(newNode); newNode = new Node(10); llist.SortedInsert(newNode); newNode = new Node(7); llist.SortedInsert(newNode); newNode = new Node(3); llist.SortedInsert(newNode); newNode = new Node(1); llist.SortedInsert(newNode); newNode = new Node(9); llist.SortedInsert(newNode); Console.WriteLine("Create Linked List"); llist.PrintList(); }} |
Javascript
class Node { constructor(data) { this.data = data; this.next = null; }}class LinkedList { constructor() { this.head = null; } sortedInsert(newNode) { if (this.head == null) { this.head = newNode; return; } let prev = null; let current = this.head; while (current != null && current.data < newNode.data) { prev = current; current = current.next; } if (prev == null) { newNode.next = this.head; this.head = newNode; } else { newNode.next = current; prev.next = newNode; } } printList() { let temp = this.head; while (temp != null) { console.log(temp.data + " "); temp = temp.next; } console.log(); }}let llist = new LinkedList();let newNode = new Node(5);llist.sortedInsert(newNode);newNode = new Node(10);llist.sortedInsert(newNode);newNode = new Node(7);llist.sortedInsert(newNode);newNode = new Node(3);llist.sortedInsert(newNode);newNode = new Node(1);llist.sortedInsert(newNode);newNode = new Node(9);llist.sortedInsert(newNode);console.log("Create Linked List");llist.printList(); |
Output
Create Linked List 1 3 5 7 9 10
The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list.
The space complexity is O(1) as it uses constant extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
