What is a Circular linked List in Data Structure?
A circular linked list is a variation of a linked list in which the last node points back to the first node, forming a loop. This allows for efficient traversal in both directions, and eliminates the need for a separate tail pointer or reference. However, it can also make some operations more complex, such as deleting a specific node, as it can be difficult to determine whether a node is the first or last in the list without additional information.
How Circular linked List Works in Data Structure?
A circular linked list works by linking the last node in the list to the first node, forming a loop. Each node in the list contains a value, as well as a reference or pointer to the next node in the list. In a circular linked list, the last node's next pointer points back to the first node, creating a circular structure.
To traverse a circular linked list, you start at the first node and follow the next pointers until you reach the first node again. This creates a loop that allows you to traverse the list indefinitely.
Insertion and deletion of nodes in a circular linked list are similar to those in a standard linked list, but with a few additional considerations. For example, when deleting a node, it's important to update the pointers of the surrounding nodes to maintain the circular structure.
In a circular linked list, there's no NULL terminator or any end of list marker to indicate the end of the list. The traversal will keep on going in a loop until the user stop it. Due to the circular structure, it's important to keep track of the starting point and the number of nodes in the list, so you can determine when to stop traversing.
Types of Circular linked List
There are two types of circular linked lists:
Single Circular Linked List: In this type, the last node points to the first node. It's a simple circular linked list.
Double Circular Linked List: In this type, the last node points to the first node and the first node points to the last node. Double circular linked list is also known as doubly circular linked list.
Both types of circular linked lists have their own advantages and disadvantages. The choice of which one to use depends on the specific requirements of the application.
Each of these types of doubly linked list have their own advantages and disadvantages, and the choice of which type to use depends on the specific requirements of the application.
Example of Circular linked List
Sure, here's a complete example of a circular linked list implementation in Java:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
this.head = null;
}
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
return;
}
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
}
public void deleteNode(int data) {
if (head == null) {
return;
}
if (head.data == data) {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = head.next;
head = current.next;
return;
}
Node current = head;
while (current.next != head && current.next.data != data) {
current = current.next;
}
if (current.next == head) {
System.out.println("Node not found");
return;
}
current.next = current.next.next;
}
public void traverse() {
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
do {
System.out.print(current.data + " ");
current = current.next;
} while
(current != head); System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.append(1);
cll.append(2);
cll.append(3);
cll.traverse();
cll.deleteNode(2);
cll.traverse();
}
}Applications of Circular linked List
Circular linked lists have a number of applications in computer science and software engineering:
Representing a Queue: Circular linked list can be used to implement a queue data structure, where elements are added at the rear and removed from the front.
Representing a Stack: Circular linked list can also be used to implement a stack data structure, where elements are added and removed from the same end.
Representing a Graph: Circular linked list can be used to represent graph nodes and edges, where each node in the list represents a vertex in the graph, and the next pointer represents an edge between two vertices.
Representing a Hash Table: Circular linked list can be used to implement a hash table data structure, where the list is used to store key-value pairs, with the key being used as the index in the list.
Dynamic memory allocation: Circular linked list can be used to implement a memory allocator, where each node represents a block of memory, with the next pointer pointing to the next free block.
Representing a circular buffer: A circular buffer is a memory buffer that is of fixed size and it stores data in a circular way, so when the buffer is full, it overwrites the oldest data. A circular linked list can be used to implement this.
Representing a tournament: A circular linked list can be used to represent a tournament where each node represents a team or a player and the next pointer represents the next opponent.
Representing a playlist: A circular linked list can be used to represent a playlist of songs or videos, where each node represents a song or video and the next pointer represents the next song or video.
Time and Space Complexity of Circular linked List
The time and space complexity of a circular linked list will depend on the specific operations being performed. Here is a brief overview of the time and space complexity of some common operations:
Insertion: Inserting a new node at the end of a circular linked list takes O(n) time on average, where n is the number of nodes in the list. This is because we need to traverse the list to find the last node before inserting the new one. However, if we are keeping a reference to the last node, this operation will take O(1) constant time.
Deletion: Deleting a node from a circular linked list takes O(n) time on average, where n is the number of nodes in the list. This is because we need to traverse the list to find the node before the one we want to delete.
Traversal: Traversing a circular linked list takes O(n) time, where n is the number of nodes in the list. This is because we need to visit each node once to print or access its data.
Searching: Searching for a specific element in a circular linked list takes O(n) time on average, where n is the number of nodes in the list. This is because we need
Advantages and Disadvantages of Circular linked List
Advantages:
Memory utilization: A circular linked list uses less memory as compared to an array because it does not waste any memory space for the next pointer of the last node.
Dynamic size: The size of a circular linked list can be changed dynamically at runtime, making it more flexible than an array.
Efficient implementation of Queue and Stack: A circular linked list can be easily used to implement queue and stack data structures, which are commonly used in computer science and software engineering.
Simple implementation of algorithms: Some algorithms such as Josephus problem can be easily implemented using circular linked list.
Efficient handling of circular data: Circular linked lists can be used to efficiently handle data that is inherently circular in nature, such as a playlist or a tournament.
Disadvantages:
Time complexity: Some operations on a circular linked list such as insertion, deletion, and searching take O(n) time on average, where n is the number of nodes in the list. This is slower than an array, which can perform these operations in O(1) constant time.
Pointer-based: A circular linked list is based on pointers, which can be difficult to understand for new programmers, and also pointer can cause problems such as memory leaks.
Extra memory space is used for storing the address of the next node
Extra time is required for traversing the linked list in order to reach the desired node.
Not cache friendly because it follows a non-contiguous memory allocation.