Circular Linked List in Java
What is Circular Linked List in Java?
In this article, we will explore what a Circular Linked List is, how it works, the main operations performed on it, sorting techniques, and complete Java code examples with inputs and outputs. By the end, you’ll have a clear understanding of how to implement and use Circular Linked Lists in Java.
While Singly and Doubly Linked Lists are commonly used, Circular Linked Lists are another powerful variant that connects the last node back to the first node, creating a circle.
Why add on another data structure and increase the hazzle?
Singly linked and doubly linked lists were easy to traverse through.
“While you cannot go back in a singly linked list, doubly linked list took a little more time when the first element was to be reached from the last element.”
Circular linked lists on the other hand are very easy to traverse through and make it easier for programmers to get results.
- CLL on the other hand have eliminated the concept of null.
- Head points to the very first element and the first node points to the second and the chain continues.
- Last node instead of pointing towards null, points to the first node making the linked list complete a imaginary circle.
What is a Circular Linked List in Java?
CLL is a variation of a linked list where the last node points back to the head (first node) instead of null. This forms a circular structure.
- In a Singly CLL, each node points to the next node, and the last node points to the first.
- In a Doubly CLL, each node has pointers to both the next and previous nodes, and the list forms a closed loop.
Features:
- There is no NULL in the list; traversal must be handled carefully.
- You can traverse the entire list from any node.
- Efficient for applications requiring a continuous loop, like task scheduling or buffering.
Basic Operations on Circular Linked List in Java:
We will implement the following operations in Java:
- Insert at the End
- Insert at the Beginning
- Delete a Node
- Traverse the List
- Sort the List
Implementation of CLL in Java
public void addNode(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
tail.nextNode = head;
}
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Java Code for Circular Linked List
Code 1: Circular Singly Linked List
- Each node has a next pointer only.
- The tail.next always points back to head, forming a circular structure.
- Insertion is done at the end.
- Traversal stops when we reach the head again.
- Efficient and lightweight – used where backward traversal is not needed.
Code 2: Circular Doubly Linked List
- Each node has both next and prev pointers.
- tail.next = head and head.prev = tail ensure circularity in both directions.
- Supports forward and backward traversal.
- Slightly more complex and memory-consuming than singly version, but more flexible.
import java.lang.*;
public class Main {
Node head = null;
Node tail = null;
// Node class
class Node {
int element;
Node next;
public Node(int element) {
this.element = element;
this.next = null;
}
}
// Add node to the list
public void add(int element) {
Node newNode = new Node(element);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head; // circular link
} else {
tail.next = newNode;
tail = newNode;
tail.next = head; // maintain circular link
}
}
// Print the list
public void print() {
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Nodes of the circular linked list:");
Node current = head;
do {
System.out.print(" " + current.element);
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
Main list = new Main();
list.add(11);
list.add(22);
list.add(33);
list.add(44);
list.print();
}
}
Output:
Nodes of the circular linked list: 11 22 33 44
import java.lang.*;
public class Main {
Node head = null;
Node tail = null;
// Node class
class Node {
int element;
Node next;
Node prev;
public Node(int element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
// Add node to the list
public void add(int element) {
Node newNode = new Node(element);
if (head == null) {
head = newNode;
tail = newNode;
head.next = head;
head.prev = head;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
tail.next = head;
head.prev = tail;
}
}
// Print the list
public void print() {
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Nodes of the doubly circular linked list:");
Node current = head;
do {
System.out.print(" " + current.element);
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
Main list = new Main();
list.add(11);
list.add(22);
list.add(33);
list.add(44);
list.print();
}
}
Output:
Nodes of the doubly circular linked list: 11 22 33 44
Space and Time Complexity in Circular Linked In Java
| Operation | Time Complexity (Singly) | Time Complexity (Doubly) | Space Complexity |
|---|---|---|---|
| Insert at Beginning | O(1) | O(1) | O(1) |
| Insert at End | O(1) | O(1) | O(1) |
| Insert at Specific Position | O(n) | O(n) | O(1) |
| Delete from Beginning | O(n) | O(1) | O(1) |
| Delete from End | O(n) | O(1) | O(1) |
| Delete Specific Node | O(n) | O(n) | O(1) |
| Search for Element | O(n) | O(n) | O(1) |
| Traverse All Nodes | O(n) | O(n) | O(1) |
Merits and Demerits of a circular linked list:
Merits:
- Any node can be accessed with easy in a circular linked list.
- Some coding problems involve a circular for which circular linked lists are optimal choice.
- Queues and advanced data structures can be implemented using circular linked list.
Demerits:
- Insertion of node in the beginning of the list is a little time consuming since it involves searching of last node to update the reference address.
- Loop control isn’t easy.
Use Cases of Circular Linked List:
- Round robin scheduling (CPU/process scheduling).
- Multiplayer games (looped turns).
- Circular buffers or memory management.
- Streaming data where buffer wrap-around is required.
FAQ's related to Circular Linked List in Java
Answer:
A Singly Linked List ends with a null pointer, while a Circular Linked List’s last node points back to the head, creating a circular structure.
Answer:
They are efficient for applications that need to cycle through data repeatedly without restarting from the head manually.
Answer:
Yes, if the head is null, the list is considered empty.
Answer:
You don’t need to detect a loop since it’s inherently circular. But if you’re unsure whether a given list is circular, Floyd’s Cycle Detection Algorithm can be used.
Answer:
Bubble sort is simple to implement, but Merge Sort is more efficient with O(n log n) time. However, Merge Sort requires extra space or pointer manipulation, which can be complex in circular structures.
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 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
Login/Signup to comment
Woah! Finally got a site that explains it all so clearly. I always used to get stuck while using circular lists, finally understood it perfectly!
Glad that we could help you. blush blush “D