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.
Fig 1: Sorted linked list

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).
Fig 2: Inserting element in linked list

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

insert node element sort single linked list
Fig 3: Insert a new node to a linked list
  • 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