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-**

Amazing, exactly what I was looking for. Thanks a ton!

ReplyDelete