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