Sorted Insert for Circular Linked List

Java Program to Insert and Sort Nodes in a Circular Linked List

In this article, we will learn how to insert nodes into a circular linked list in such a way that the list stays sorted at all times. For performing this operation we should be aware of “Insert nodes at various positions in a circular linked list” process.

On that knowledge to create a Java program that performs a sorted insertion. This means that every time you add a new node, the program will automatically insert it in the right position to keep the list in ascending order. This approach saves us from having to sort the list after all nodes have been added.

Sorted Insert In Circular Linked List
Sorted Insert In Circular Linked List

Sorted Insert for Circular Linked List in Java

Sorted insert operation ensures that each new node is inserted in its correct position to maintain ascending order.

When inserting a new node:

  • If the list is empty, the node points to itself.
  • And If the new data is smaller than the head data, insert before the head and update the head.
  • Otherwise, find the correct position to insert such that order is preserved.

Assume a class Node with:

  1. int data: holds the value
  2. Node next: reference to the next node

Algorithm for Sorted Insert for Circular Linked List

  1. Create a new node newNode with the given value.

  2. If the list is empty:

    • Make newNode.next = newNode

    • Set head = newNode

  3. And If the new value is less than or equal to head.data:

    • Traverse to the last node curr such that curr.next == head

    • Insert newNode before head and update head

  4. Otherwise:

    • Traverse the list using curr to find the appropriate position.

    • Insert newNode after curr and before curr.next.

Java Program for Sorted Insert in Circular Linked List

Run
class SortedCircularLinkedList {

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head = null;

    public void sortedInsert(int value) {
        Node newNode = new Node(value);

        if (head == null) {
            newNode.next = newNode;
            head = newNode;
            return;
        }

        Node curr = head;

        // Insertion before the head (smallest element)
        if (value <= head.data) {
            while (curr.next != head) {
                curr = curr.next;
            }
            curr.next = newNode;
            newNode.next = head;
            head = newNode;
        } else {
            // Locate the node before the point of insertion
            while (curr.next != head && curr.next.data < value) {
                curr = curr.next;
            }
            newNode.next = curr.next;
            curr.next = newNode;
        }
    }

    public void printList() {
        if (head == null) return;
        Node temp = head;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }

    public static void main(String[] args) {
        SortedCircularLinkedList list = new SortedCircularLinkedList();
        list.sortedInsert(30);
        list.sortedInsert(20);
        list.sortedInsert(50);
        list.sortedInsert(10);
        list.sortedInsert(40);

        System.out.println("Sorted Circular Linked List:");
        list.printList();
    }
}

Sample Input and Output:

Input Sequence:
30, 20, 50, 10, 40

Output:
Sorted Circular Linked List:
10 20 30 40 50

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code for Sorted Insert In Circular Linked List in Java

Now we have shared two codes, for Sorted Insert in Circular Linked List using Java for:

Code 1: For Sorted Insertion in a Singly Circular Linked List

Demonstrates how to perform sorted insertion in a singly circular linked list using Java. In a singly circular linked list, each node points to the next node, and the last node points back to the first node (head), forming a circle.

Code 2: For Sorted Insertion in a Doubly Circular Linked List

To implement a doubly circular linked list, where each node should have a next and prev pointer. However, in practice, it functions exactly like a singly circular linked list.

To wrap it up….

  1. Sorted insertion in a circular linked list is a crucial operation when maintaining order in dynamic data structures.
  2. It eliminates the need for post-sorting and ensures that the list remains sorted at all times.
  3. By understanding the step by step logic and implementing it in Java, developers can efficiently manage ordered circular linked lists in various applications.

FAQ's related to Sub array with Given Sum

Answer:

  1. Sorted insertion means inserting a new node in its correct position such that the list remains sorted in ascending (or descending) order.
  2. Instead of adding nodes randomly and sorting later, we maintain order during insertion.
  3. This saves time and avoids extra sorting steps, especially useful in real time or memory constrained systems.

Answer:

  1. Purpose of sorted insertion is to maintain the elements of a circular linked list in sorted (ascending or descending) order at all times.
  2. Instead of inserting elements randomly and sorting them later, each new node is placed directly in its correct position.
  3. This helps in scenarios where frequent insertions occur and a sorted list is always required (e.g., priority queues, real time systems).

Answer:

Sorted insertion affects multiple pointers:

  • Breaking or forgetting to update any next or prev pointer can lead to infinite loops or unreachable nodes.
  • In a circular structure, you must ensure that:
  1. The last node points back to the head.
  2. For doubly lists, prev pointers also maintain circularity.
    Accurate pointer handling keeps the list circular, sorted, and safe for further operations.

 

Answer:

Yes, duplicates can be inserted in a sorted circular linked list.
The sorted insertion algorithm places the new node after the last occurrence of nodes with smaller or equal values, depending on the implementation.

Answer:

The time complexity of sorted insertion in a circular linked list is:

O(n) in the worst case, where n is the number of nodes in the list.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List