Introduction
When dealing with data structures in Java, linked lists are a powerful tool, providing efficient ways to manage and organize data. While most programmers are familiar with singly and doubly linked lists, the circular linked list is an equally important variation that has unique characteristics and applications. In this comprehensive guide, we’ll explore circular linked lists, understand their structure, and walk through a complete Java implementation. To learn more about linked lists, click here.
What is a Circular Linked List?
A circular linked list is a type of linked list where the last node points back to the first node, forming a closed loop. Unlike singly linked lists, which end with a null reference, a circular linked list loops around, making it ideal for situations where the data structure needs to operate in a continuous or cyclical manner.
In a circular linked list, you can traverse the entire list from any node without needing a starting or ending point.
Benefits of Circular Linked Lists
- Efficient Looping: Circular lists naturally handle scenarios that require repeated or cyclical access, such as managing processes in round-robin scheduling.
- Flexible Insertion and Deletion: Adding or removing elements in a circular linked list is straightforward, as each node points to the next, allowing easy modifications.
- Bidirectional Traversal Option: By combining with a doubly linked list structure, a circular linked list can support both forward and backward traversal, enhancing flexibility.
Types of Circular Linked Lists
There are two main types of circular linked lists:
- Singly Circular Linked List: In this type, each node has a single pointer pointing to the next node, with the last node pointing back to the head.
- Doubly Circular Linked List: Each node has two pointers, one to the next node and one to the previous node, with both ends connected in a circular manner.
In this post, we’ll focus on implementing a Singly Circular Linked List in Java.
Implementing Circular Linked Lists in Java
To build a circular linked list in Java, we’ll need a Node class and a CircularLinkedList class to manage the list.
Step 1: Define the Node Class
Each node in our circular linked list will contain:
- Data: The actual value stored in the node.
- Next: A reference to the next node in the list.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}Step 2: Create the CircularLinkedList Class
This class will manage our circular linked list and implement methods to insert, delete, and display nodes.
Code Explanation and Methods
Here is the complete Java code to implement a circular linked list, with methods for insertion, deletion, and traversal.
Insertions in a Circular Linked List
We’ll create two insertion methods:
- Insert at the Beginning: This inserts a new node at the start and updates the last node to point to the new head.
- Insert at the End: This adds a new node after the last node and connects it back to the head.
class CircularLinkedList {
Node head = null;
Node tail = null;
// Insert a node at the beginning
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
newNode.next = head;
head = newNode;
tail.next = head;
}
}
// Insert a node at the end
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
tail.next = newNode;
tail = newNode;
tail.next = head;
}
}
}Deleting Nodes in a Circular Linked List
Our delete methods will handle:
- Delete from Beginning: Removes the head node and updates the last node to point to the new head.
- Delete by Value: Locates the node with the specified value and removes it from the list.
// Delete the first node
public void deleteAtBeginning() {
if (head != null) {
if (head == tail) { // only one node
head = null;
tail = null;
} else {
head = head.next;
tail.next = head;
}
}
}
// Delete a node by value
public void deleteByValue(int data) {
if (head == null) return;
Node current = head;
Node previous = null;
do {
if (current.data == data) {
if (current == head) {
deleteAtBeginning();
} else {
previous.next = current.next;
if (current == tail) {
tail = previous;
}
}
return;
}
previous = current;
current = current.next;
} while (current != head);
}Displaying a Circular Linked List
To traverse and display a circular linked list, we’ll create a method that iterates through each node until it returns to the head node.
// Display the circular linked list
public void display() {
if (head == null) {
System.out.println("The list is empty.");
return;
}
Node current = head;
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != head);
System.out.println("(back to head)");
}
}Complete Java Program for Circular Linked List
Here’s the entire code in one place:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head = null;
Node tail = null;
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
newNode.next = head;
head = newNode;
tail.next = head;
}
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head;
} else {
tail.next = newNode;
tail = newNode;
tail.next = head;
}
}
public void deleteAtBeginning() {
if (head != null) {
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
tail.next = head;
}
}
}
public void deleteByValue(int data) {
if (head == null) return;
Node current = head;
Node previous = null;
do {
if (current.data == data) {
if (current == head) {
deleteAtBeginning();
} else {
previous.next = current.next;
if (current == tail) {
tail = previous;
}
}
return;
}
previous = current;
current = current.next;
} while (current != head);
}
public void display() {
if (head == null) {
System.out.println("The list is empty.");
return;
}
Node current = head;
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != head);
System.out.println("(back to head)");
}
}
public class Main {
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtBeginning(5);
System.out.println("Circular Linked List:");
list.display();
list.deleteByValue(20);
System.out.println("After deleting 20:");
list.display();
list.deleteAtBeginning();
System.out.println("After deleting from beginning:");
list.display();
}
}Output:
Circular Linked List:
5 -> 10 -> 20 -> 30 -> (back to head)
After deleting 20:
5 -> 10 -> 30 -> (back to head)
After deleting from beginning:
10 -> 30 -> (back to head)Use Cases of Circular Linked Lists
Circular linked lists are invaluable for situations where operations need to cycle repeatedly through data, and they are commonly used in:
- Round-Robin Scheduling: Circular linked lists make it easy to rotate through processes in a continuous loop, providing each process a fair share of time on a system.
- Buffer Management: In applications that use buffers, such as streaming or networking, circular linked lists can help manage buffers in a cyclical manner without needing to reset pointers.
- Playlist or Media Players: Circular lists are ideal for applications like music or video players that loop playlists, as they can seamlessly move from the last to the first item.
- Games and Multiplayer Systems: For tracking turns in multiplayer games, a circular linked list enables cycling through players continuously without interruption.
Conclusion
Circular linked lists bring flexibility and efficiency to data structures, especially for applications requiring repeated, cyclical access to elements. In this guide, we covered the fundamentals of circular linked lists, types, and practical Java implementation. With our step-by-step code examples, you can now confidently add, delete, and traverse nodes in a circular linked list in Java.
Mastering circular linked lists opens the door to handling a wide range of cyclical data tasks, and understanding this data structure equips you with a versatile tool for advanced programming scenarios. Happy coding!