Insert element/node to sorted singly linked list in java (example/ algorithm)

• Given a sorted singly linked containing elements.
• Insert a new node to a single linked list such that linked list remains sorted.
• Iterate through the single linked list & find the appropriate place to insert a element.
  • Linked list should remain sorted after insertion.
• Traverse the sorted singly linked list to insert new element using iterative (non recursive) algorithm.

Algorithm: insert element to a sorted singly linked list.

• Take backup of head node
• Suppose, we would like to insert a new node 4 in a linked list [shown in Fig 1]
• Start iterating the linked list from head node
  • Compare first node with new node [element 4]
    • 1 < 4 ? Its true, take the back of node 1.
  • Compare second node with new node [element 4]
    • 3 < 4 ? Its true, take the back of node 3.
  • Compare third node with new node [element 4]
    • 5 < 4 ? Its false, node should be inserted node 5
      
    • Insert a node 4 before Node 5
    • Rearrange the references, so that 4 inserted in linked list
  • return the head node of linked list
  • We have shown the above algorithm in Fig 2.
  • Time complexity of algorithm is O (n).

Similarly, we can apply above algorithm to insert new element 7 in a linked list. We have shown it in Fig 3.

• print function will print the linked list.
• insert function will insert a new node to a sorted linked list.

Program: insert node/ element to a sorted singly linked list in java

1.) InsertInSortedList class:

• InserInSortedList class is responsible for inserting new node to single linked list.
• We will traverse the single linked and find out the appropriate place, to insert new node in a linked list.

package org.learn.Question;

public class InsertInSortedList {

 public static Node insert(Node head, Node newNode) {
  
  // first node to be inserted
  if (null == head) {
   return newNode;
  }
  
  Node prev = null;
  Node iter = head;
  
  while (iter != null && iter.data < newNode.data) {
   // take backup of prev node
   // used in appending the new node
   prev = iter;
   iter = iter.next;
  }
  
  newNode.next = prev.next;
  prev.next = newNode;
  return head;
 }

 public static void prepareList(Node head, int data) {
  
  while (head.next != null)
   head = head.next;
  head.next = new Node(data);
 }

 public static void print(Node head) {
  
  while (head != null) {
   System.out.printf("%d ", head.data);
   head = head.next;
  }
  System.out.println("");
 }
}

2.) SingleLinkedListClient Class:

We are performing following operation in SingleLinkedListClient class

1. We are creating the singlelinked list as shown in Fig 1.
2. InsertInSortedList.insert method will insert a new node to sorted single linked list
3. We are printing the final single linked list.

package org.learn.Client;

import org.learn.Question.InsertInSortedList;
import org.learn.Question.Node;

public class SingleLinkedListClient {
 
 public static void main(String[] args) {
  
  int[] listData = { 1, 3, 5, 9 };
  Node head = new Node(listData[0]);
  
  for (int count = 1; count < listData.length; count++) {
   InsertInSortedList.prepareList(head, listData[count]);
  }
  
  System.out.printf("1. Single linked list is : ");
  InsertInSortedList.print(head);

  int newData = 4;
  Node newNode = new Node(newData);
  head = InsertInSortedList.insert(head, newNode);
  System.out.printf("2. Single linked list after inserting %d is : ", newData);
  InsertInSortedList.print(head);

  newData = 7;
  newNode = new Node(newData);
  head = InsertInSortedList.insert(head, newNode);
  System.out.printf("3. Single linked list after inserting %d is : ", newData);
  InsertInSortedList.print(head);
 }
}

3.) Node Class:

• Node class representing the node(s) of single linked list

package org.learn.Question;

public class Node {
 public int data;
 public Node next;

 public Node(int num) {
  this.data = num;
  this.next = null;
 }
}

Output: insert a node/element to a sorted singly linked list in java

1. Single linked list is : 1 3 5 9 
2. Single linked list after inserting 4  is : 1 3 4 5 9 
3. Single linked list after inserting 7 is : 1 3 4 5 7 9 

Download example Code – Insert node/element to a sorted linked list