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.
In a sorted circular linked list, nodes are maintained in ascending order based on their data values.
This article focuses on performing a sorted insert operation, where each new node is inserted in its correct position to maintain the sorted order.
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:
- int data: holds the value
- Node next: reference to the next node
Algorithm for Sorted Insert for Circular Linked List
Create a new node
newNodewith the given value.If the list is empty:
Make
newNode.next = newNodeSet
head = newNode
And If the new value is less than or equal to
head.data:Traverse to the last node
currsuch thatcurr.next == headInsert
newNodebeforeheadand updatehead
Otherwise:
Traverse the list using
currto find the appropriate position.Insert
newNodeaftercurrand beforecurr.next.
Java Program for Sorted Insert in Circular Linked List
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
Space Complexity: O(1)
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.
public class SinglyCircularLinkedList {
public static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
Node head = null;
void sortedInsert(int value) {
Node newNode = new Node(value);
if (head == null) {
newNode.next = newNode;
head = newNode;
} else if (value < head.data) {
Node current = head;
while (current.next != head)
current = current.next;
current.next = newNode;
newNode.next = head;
head = newNode;
} else {
Node current = head;
while (current.next != head && current.next.data < value)
current = current.next;
newNode.next = current.next;
current.next = newNode;
}
}
void printList() {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node current = head;
System.out.print("Singly Circular Linked List: ");
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
SinglyCircularLinkedList list = new SinglyCircularLinkedList();
list.sortedInsert(10);
list.sortedInsert(30);
list.sortedInsert(20);
list.sortedInsert(5);
list.sortedInsert(25);
list.printList(); // Output should be: 5 10 20 25 30
list.sortedInsert(15);
System.out.println("After inserting 15:");
list.printList(); // Output: 5 10 15 20 25 30
}
}
Output
Singly Circular Linked List: 5 10 20 25 30 After inserting 15: Singly Circular Linked List: 5 10 15 20 25 30
public class DoublyCircularLinkedList {
public static class Node {
int data;
Node next, prev;
Node(int data) {
this.data = data;
}
}
Node head = null;
void sortedInsert(int value) {
Node newNode = new Node(value);
if (head == null) {
newNode.next = newNode.prev = newNode;
head = newNode;
} else if (value < head.data) {
Node tail = head.prev;
newNode.next = head;
newNode.prev = tail;
head.prev = newNode;
tail.next = newNode;
head = newNode;
} else {
Node current = head;
while (current.next != head && current.next.data < value)
current = current.next;
newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;
}
}
void printList() {
if (head == null) {
System.out.println("List is empty.");
return;
}
Node current = head;
System.out.print("Doubly Circular Linked List: ");
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
DoublyCircularLinkedList list = new DoublyCircularLinkedList();
list.sortedInsert(10);
list.sortedInsert(30);
list.sortedInsert(20);
list.sortedInsert(5);
list.sortedInsert(25);
list.printList(); // Output: 5 10 20 25 30
list.sortedInsert(15);
System.out.println("After inserting 15:");
list.printList(); // Output: 5 10 15 20 25 30
}
}
Output
Doubly Circular Linked List: 5 10 20 25 30 After inserting 15: Doubly Circular Linked List: 5 10 15 20 25 30
To wrap it up….
- Sorted insertion in a circular linked list is a crucial operation when maintaining order in dynamic data structures.
- It eliminates the need for post-sorting and ensures that the list remains sorted at all times.
- 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:
- Sorted insertion means inserting a new node in its correct position such that the list remains sorted in ascending (or descending) order.
- Instead of adding nodes randomly and sorting later, we maintain order during insertion.
- This saves time and avoids extra sorting steps, especially useful in real time or memory constrained systems.
Answer:
- Purpose of sorted insertion is to maintain the elements of a circular linked list in sorted (ascending or descending) order at all times.
- Instead of inserting elements randomly and sorting them later, each new node is placed directly in its correct position.
- 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:
- The last node points back to the head.
- 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
Circular Linked List
- Introduction to Circular Linked List
Click Here - Circular Linked List Applications
Click Here - Circular Linked List in –
- Insertion in Circular Linked List –
- Insertion at the beginning–
- Insertion at the end –
- Insertion at nth position –
- Deletion in Circular Linked List –
- Deletion from beginning in Circular Linked List –
- Deletion from nth position in Circular Linked List –
- Deletion from end in Circular Linked List –
- Insertion and Deletion in Circular Linked List – C | C++ | Java
- Split a Circular Linked List in two halves –
- Count nodes in Circular Linked List –
- Sorted Insert In Circular Linked List –
- Insertion in the middle in Circular Linked List –
Circular Linked List
- Introduction to Circular Linked List
- Circular Linked List Applications
- Circular Linked List in – C | C++ | Java
- Insertion in Circular Linked List – C | C++ | Java
- Deletion in Circular Linked List – C | C++ | Java
- Insertion and Deletion in a 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
Login/Signup to comment