Sorted Insert for Circular Linked List

February 21, 2023

Sorted Insert In Circular Linked List

JAVA Program to Sort a Circular Linked List while Inserting Nodes in it

As we’ve learned in the earlier pages that Insertion can be done at various Positions in a Circular Linked List. In this page we’ll learn how we can use those techniques to create program using which we can insert nodes in a Circular Linked List and Sort the list Simultaneously. Below is a Solution in the form of a JAVA Program for Sorted Insert for Circular Linked List along with a detailed analysis of example.

Algorithm that will be used in the Program below

  • sortedInsert(Node nextNode)
  • Node thisNode = head
  • IF thisNode == null
    • nextNode->next = nextNode
    • head = nextNode
  • ELSE IF (thisNode->element >= nextNode->element)
    • FOR i=0 until thisNode->next != head
      • thisNode = thisNode->next
    • thisNode->next = nextNode
    • nextNode->next = head
    • head = nextNode
  • ELSE
    • WHILE thisNode->next != head && thisNode->next->element < nextNode-> element
      • thisNode = thisNode->next
      • nextNode->next = thisNode->next
      • thisNode->next = nextNode
  • EXIT
void sortedInsert(int n)
    {
        Node nextNode=new Node(n);
        Node thisNode = head;
        if (thisNode == null)
        {
            nextNode.next = nextNode;
            head = nextNode;
        }
        else if (thisNode.element >= nextNode.element)
        {
            for (int i=0; thisNode.next != head; i++)
                thisNode = thisNode.next;
            thisNode.next = nextNode;
            nextNode.next = head;
            head = nextNode;
        }
        else
        {
            while (thisNode.next != head && thisNode.next.element < nextNode.element)
                thisNode = thisNode.next;
            nextNode.next = thisNode.next;
            thisNode.next = nextNode;
        }
    }
Sorted Insert In Circular Linked List
DSA desktop gif
DSA mobile gif

Deletion in Circular Linked List

Deletion from beginning in Circular Linked List

Insertion and Deletion in a Circular Linked List

Insertion in the middle in Circular Linked List

Code for Sorted Insert In Circular Linked List in JAVA

Run 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.sortedInsert(10);
        Obj.sortedInsert(20);
        Obj.sortedInsert(30);
        Obj.sortedInsert(40);
        Obj.sortedInsert(50);
        Obj.sortedInsert(60);

        Obj.print();

        System.out.println("Linked List after insertion : ");
        Obj.sortedInsert(33);
        Obj.print();
    }
    public static class Node{
        int element;
        Node next;

        public Node(int element) {
            this.element = element;
        }
    }
    int cnt;
    static Node list1, list2;
    public Node head = null;
    public Node tail = null;
    public void print() {
        Node current = head;
        if(head == null) {
            System.out.println("Empty List");
        }
        else {
            System.out.println("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println("\n");
        }
    }

    void sortedInsert(int n)
    {
        Node nextNode=new Node(n);
        Node thisNode = head;
        if (thisNode == null)
        {
            nextNode.next = nextNode;
            head = nextNode;
        }
        else if (thisNode.element >= nextNode.element)
        {
            for (int i=0; thisNode.next != head; i++)
                thisNode = thisNode.next;
            thisNode.next = nextNode;
            nextNode.next = head;
            head = nextNode;
        }
        else
        {
            while (thisNode.next != head && thisNode.next.element < nextNode.element)
                thisNode = thisNode.next;
            nextNode.next = thisNode.next;
            thisNode.next = nextNode;
        }
    }
}

Output

Circular Linked List is
 10 20 30 40 50 60

Linked List after insertion : 
Circular Linked List is
 10 20 30 33 40 50 60
Run 
import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.sortedInsert(10);
        Obj.sortedInsert(20);
        Obj.sortedInsert(30);
        Obj.sortedInsert(40);
        Obj.sortedInsert(50);
        Obj.sortedInsert(60);

        System.out.println("Original List");
        Obj.print();

        Obj.sortedInsert(33);
        System.out.println("List after insertion");
        Obj.print();
    }
    public static class Node{
        int element;
        Node next;
        Node prev;

        public Node(int element) {
            this.element = element;
        }
    }

    public Node head = null;
    public Node tail = null;

    public void print() {
        Node current = head;
        if(head == null) {
            System.out.println("Empty List");
        }
        else {
            System.out.println("Circular Linked List is");
            do{
                //Prints each node by incrementing pointer.
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println("\n");
        }
    }

    void sortedInsert(int n)
    {
        Node nextNode=new Node(n);
        Node thisNode = head;
        if (thisNode == null)
        {
            nextNode.next = nextNode;
            head = nextNode;
        }
        else if (thisNode.element >= nextNode.element)
        {
            for (int i=0; thisNode.next != head; i++)
                thisNode = thisNode.next;
            thisNode.next = nextNode;
            nextNode.next = head;
            head = nextNode;
        }
        else
        {
            while (thisNode.next != head && thisNode.next.element < nextNode.element)
                thisNode = thisNode.next;
            nextNode.next = thisNode.next;
            thisNode.next = nextNode;
        }
    }
}

Output

Original List
Circular Linked List is
 10 20 30 40 50 60

List after insertion
Circular Linked List is
 10 20 30 33 40 50 60

Prime Course Trailer

Related Banners

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

Get Prime

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

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