Sorted Insert for Circular Linked List

Insertion in Java

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

Code in JAVA Programming Language

Run
import java.util.*;
public class Main 
{ 
    Node head;
    Main() 
    { 
        head = null;
    } 
    void sortedInsert(Node nextNode) 
    { 
        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; 
        } 
    }
    public void print() {  
        Node temp = head;    
        if(head == null) {  
            System.out.println("null");  
        }  
        else {
            do{ 
                System.out.print(temp.element+ " ");  
                temp = temp.next;  
            }while(temp != head);  
            System.out.println();  
        } 
     }
    public static void main(String[] args) 
    { 
        Main ll = new Main(); 
        Scanner s = new Scanner(System.in);
        Node temp = null;
        System.out.println("Enter 6 elements of the Circular Linked List");
        for (int i = 0; i < 6; i++) 
        { 
            temp = new Node(s.nextInt()); 
            ll.sortedInsert(temp); 
        } 
        System.out.println("\nSorted Circular Linked List");
        ll.print(); 
    } 
} 
class Node 
{ 
    int element; 
    Node next; 
    Node(int e) 
    { 
        element = e; 
        next = null; 
    } 
}

Enter 6 elements of the Circular Linked List
1
4
6
3
2
3

Sorted Circular Linked List
1 2 3 3 4 6