Sorted Linked List In Java Program

In this post we’ll see an implementation of sorted Linked List in Java. In a sorted linked list data is maintained in sorted order. For each insertion in the sorted list, item needs to be inserted at the appropriate location. You need to find the first item that is greater than the inserted item (in case of ascending order) and element should be inserted just before that item.

Java program for Sorted Linked List

In the Java program for sorted list there are two operations.

Insertion in the sorted list
Removing first item from the list (deleting minimum value).

For representing nodes of the linked list a separate class is used which apart from the data also holds a reference to itself.

static class Node{
 //data
 int i;
 // Reference to next node
 Node next;
}

In the sorted list class there is also a reference head of type Node that points to the first node of the sorted list.

Insertion in the sorted list

For insertion in the sorted linked list 2 references are maintained previous and current, you start with-

Node current = head;
Node previous = null;

Then you keep moving through the nodes while the inserted data is greater than the data stored in the traversed node.

while(current != null && data > current.i){
  previous = current;
  current = current.next;
}

At that location new node is inserted so that the previous node starts pointing to the new node and new node points to the current node.

previous.next = newNode;
newNode.next = current;

Following image shows how insertion in sorted linked list works.

Sorted Linked List – Full Java program

public class SortedLinkedList {
  // reference to first node
  private Node head;
  SortedLinkedList(){
    head = null;
  }
  // Class for nodes
  static class Node{
    //data
    int i;
    Node next;
    Node(int i){
      this.i = i;
      this.next = null;
    }
    public void displayData(){
      System.out.print(i + " ");
    }
  }
    
  public void insert(int data){
    Node newNode = new Node(data);
    Node current = head;
    Node previous = null;
    while(current != null && data > current.i){
      previous = current;
      current = current.next;
    }
    // insertion at beginning of the list
    if(previous == null){
      head = newNode;
    }else{
      previous.next = newNode;
    }
    newNode.next = current;
  }
    
  public Node remove(){
    if(head == null){
      throw new RuntimeException("List is empty..");
    }
    Node temp = head;
    head = head.next;
    return temp;
  }
    
  // Method to traverse and display all nodes
  public void displayList(){
    Node current = head;
    while(current != null){
      current.displayData();
      current = current.next;
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    SortedLinkedList list = new SortedLinkedList();
    list.insert(10);
    list.insert(30);
    list.insert(60);
    System.out.println("After initial insertions--");
    list.displayList();
    list.insert(20);
    list.insert(40);
    list.insert(5);
    list.insert(70);
    System.out.println("After insertions--");
    list.displayList();
    Node node = list.remove();
    System.out.println("Item removed-- " + node.i);
    list.displayList();
  }
}

Output

After initial insertions--
10 30 60 
After insertions--
5 10 20 30 40 60 70 
Item removed-- 5
10 20 30 40 60 70

That's all for this topic Sorted Linked List In Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Tuesday, May 24, 2022