Friday, March 1, 2019

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.

  1. Insertion in the sorted list
  2. 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 In Java

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

  1. Doubly Linked List Implementation Java Program
  2. How to Reverse a Linked List in Java
  3. Ternary Search Program in Java
  4. Converting Numbers to Words - Java Program
  5. Print Odd-Even Numbers Using Threads And wait-notify - Java Program

You may also like-

  1. Getting All The Schemas in a DB - Java Program
  2. Converting String to Byte Array - Java Program
  3. Find Largest and Second Largest Number in Given Array - Java Program
  4. Java Lambda Expression Comparator Example
  5. CompletableFuture in Java With Examples
  6. AutoBoxing And UnBoxing in Java
  7. Association, Aggregation And Composition in Java
  8. Spring Profiles With Examples