Site icon

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

Fig 1: Sorted linked list

Algorithm: insert element to a sorted singly linked list.

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

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

1.) InsertInSortedList class:

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:

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

Exit mobile version