Circular Linked List in Data Structures: An Overview
If you require a data structure to retain an organized series of records, consider using a circular linked list. Circular Linked List in Data Structures has no obvious beginning or conclusion and cycles back on itself, unlike ordinary linked lists. When used correctly, it provides benefits for specific applications. This article will provide you with an overview of circular linked lists, their advantages, and how to use them in your applications.
What is a circular linked list in data structures?
In computer science and programming, data structures are critical for data management. Circular linked lists are a type of data structure in which items form a circle, with the last node referring back to the beginning. They're useful for situations that require circular data processing, such as rotations or looping. Despite their initial complexity, circular linked lists dramatically improve code efficiency.
Types of Circular Linked List in Data Structures
There are three types of Circular Linked List in Data Structures:
Singly-linked circular list:
In this type of circular linked list, each node has only one pointer, which points to the next node in the sequence. The last node in the list points back to the first node to create a circular structure.
Doubly linked circular list:
In this type of circular linked list, each node has two pointers, one that points to the next node and another that points to the previous node. The first node's previous pointer points to the last node, and the last node's next pointer points to the first node to form a circular structure.
Circular linked list with a header node:
In this type of circular linked list, an extra node is added at the beginning of the list that serves as a header node. The header node does not contain any data, and its next pointer points to the first node in the list. The last node in the list points back to the header node to create a circular structure. This type of list is useful in situations where the number of nodes in the list is unknown or can change dynamically.
Memory Representation of circular linked list
- A circular linked list is a unique data structure, where the last node of the list is connected to the first node, forming a loop.
- This loop ensures that the list can be traversed endlessly without ever reaching a null pointer.
- The memory representation of a circular linked list is quite different from that of a regular linked list since a circular linked list does not have a null pointer to indicate the end of the list.
- Instead, a pointer in one of the nodes points to the starting node of the list, forming this endless loop.
- This representation offers a lot of flexibility when working with data, and is often used in various computer science applications, such as operating systems and memory management systems.
- The circular linked list allows for dynamic memory allocation and easy manipulation of data in real-time systems, making it a powerful tool in the computer science field.
Operations on circular linked list
Similar to the singly linked list, the circular linked list allows us to do the following operations:
- Insertion
- Deletion
Insertion
Any new Node should be able to be inserted into the provided circular linked list.
Insertion at the beginning of the list
- In order to maintain the circular structure when adding at the beginning of a circular linked list, you need to update the next pointer of the last node to point to the new first node.
- Make sure the new node's next pointer points to the list's current head and update the list head to the new node.
Insertion at the end of the list
- When inserting at the end, you must iterate the list to locate the final node (the one whose next pointer goes to the head).
- Update the last node's next pointer so that it points to the new node.
- Maintaining circularity requires that the new node's next pointer point back towards the head.
Insertion in between the nodes
- In order to insert a new node between nodes, you often need to locate the node that comes before it.
- Make certain that the new node's next pointer points to the node that comes after it.
- Redirect the next pointer of the node that comes before the new node to the new node.
Deletion
There are three possible ways for deleting a specific node from a circular linked list.
If it's the only node in the Circular Linked List
- Set the list's head to Null after removing the sole node to make it clear that the list is now empty.
If the Node to be deleted is the last node in the Circular Linked List
- In order to delete the last node, you must locate the node that points to it (the last node's precursor).
- Delete the preceding node and update the predecessor node's next pointer to point to the new last node. The circular connection is broken in this way.
- The final node should be deleted.
Deleting any other node in the Circular Linked List
- You must navigate the list until you discover the node you would like to delete, except the first and last nodes.
- The node to be deleted is effectively removed from the circular list by updating the next reference of the preceding node to skip over it.
- Depending on your programming language, make sure to correctly manage memory by deallocating the memory of the deleted node if necessary.
Circular Linked List Code in Python, Java, and C++
# Python code to perform circular linked list operations
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.last = None
def addToEmpty(self, data):
if self.last != None:
return self.last
# allocate memory to the new node and add data to the node
newNode = Node(data)
# assign last to newNode
self.last = newNode
# create link to iteself
self.last.next = self.last
return self.last
# add node to the front
def addFront(self, data):
# check if the list is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the current first node in the newNode
newNode.next = self.last.next
# make newNode as last
self.last.next = newNode
return self.last
# add node to the end
def addEnd(self, data):
# check if the node is empty
if self.last == None:
return self.addToEmpty(data)
# allocate memory to the new node and add data to the node
newNode = Node(data)
# store the address of the last node to next of newNode
newNode.next = self.last.next
# point the current last node to the newNode
self.last.next = newNode
# make newNode as the last node
self.last = newNode
return self.last
# insert node after a specific node
def addAfter(self, data, item):
# check if the list is empty
if self.last == None:
return None
newNode = Node(data)
p = self.last.next
while p:
# if the item is found, place newNode after it
if p.data == item:
# make the next of the current node as the next of newNode
newNode.next = p.next
# put newNode to the next of p
p.next = newNode
if p == self.last:
self.last = newNode
return self.last
else:
return self.last
p = p.next
if p == self.last.next:
print(item, "The given node is not present in the list")
break
# delete a node
def deleteNode(self, last, key):
# If linked list is empty
if last == None:
return
# If the list contains only a single node
if (last).data == key and (last).next == last:
last = None
temp = last
d = None
# if last node is to be deleted
if (last).data == key:
# find the node before the last node
while temp.next != last:
temp = temp.next
# point temp node to the next of last i.e. first node
temp.next = (last).next
last = temp.next
# travel to the node to be deleted
while temp.next != last and temp.next.data != key:
temp = temp.next
# if node to be deleted was found
if temp.next.data == key:
d = temp.next
temp.next = d.next
return last
def traverse(self):
if self.last == None:
print("The list is empty")
return
newNode = self.last.next
while newNode:
print(newNode.data, end=" ")
newNode = newNode.next
if newNode == self.last.next:
break
# Driver Code
if __name__ == "__main__":
cll = CircularLinkedList()
last = cll.addToEmpty(6)
last = cll.addEnd(8)
last = cll.addFront(2)
last = cll.addAfter(10, 2)
cll.traverse()
last = cll.deleteNode(last, 8)
print()
cll.traverse()
// Java code to perform circular linked list operations
class CircularLinkedList {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node last, int data) {
if (last != null)
return last;
// allocate memory to the new node
Node newNode = new Node();
// assign data to the new node
newNode.data = data;
// assign last to newNode
last = newNode;
// create link to iteself
newNode.next = last;
return last;
}
// add node to the front
static Node addFront(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the current first node in the newNode
newNode.next = last.next;
// make newNode as head
last.next = newNode;
return last;
}
// add node to the end
static Node addEnd(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the head node to next of newNode
newNode.next = last.next;
// point the current last node to the newNode
last.next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
static Node addAfter(Node last, int data, int item) {
if (last == null)
return null;
Node newNode, p;
p = last.next;
do {
// if the item is found, place newNode after it
if (p.data == item) {
// allocate memory to the new node
newNode = new Node();
// add data to the node
newNode.data = data;
// make the next of the current node as the next of newNode
newNode.next = p.next;
// put newNode to the next of p
p.next = newNode;
// if p is the last node, make newNode as the last node
if (p == last)
last = newNode;
return last;
}
p = p.next;
} while (p != last.next);
System.out.println(item + "The given node is not present in the list");
return last;
}
// delete a node
static Node deleteNode(Node last, int key) {
// if linked list is empty
if (last == null)
return null;
// if the list contains only a single node
if (last.data == key && last.next == last) {
last = null;
return last;
}
Node temp = last, d = new Node();
// if last is to be deleted
if (last.data == key) {
// find the node before the last node
while (temp.next != last) {
temp = temp.next;
}
// point temp node to the next of last i.e. first node
temp.next = last.next;
last = temp.next;
}
// travel to the node to be deleted
while (temp.next != last && temp.next.data != key) {
temp = temp.next;
}
// if node to be deleted was found
if (temp.next.data == key) {
d = temp.next;
temp.next = d.next;
}
return last;
}
static void traverse(Node last) {
Node p;
if (last == null) {
System.out.println("List is empty.");
return;
}
p = last.next;
do {
System.out.print(p.data + " ");
p = p.next;
}
while (p != last.next);
}
public static void main(String[] args) {
Node last = null;
last = addToEmpty(last, 6);
last = addEnd(last, 8);
last = addFront(last, 2);
last = addAfter(last, 10, 2);
traverse(last);
deleteNode(last, 8);
traverse(last);
}
}
// C++ code to perform circular linked list operations
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data) {
if (last != NULL) return last;
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to the new node
newNode->data = data;
// assign last to newNode
last = newNode;
// create link to iteself
last->next = last;
return last;
}
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the current first node in the newNode
newNode->next = last->next;
// make newNode as head
last->next = newNode;
return last;
}
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the head node to next of newNode
newNode->next = last->next;
// point the current last node to the newNode
last->next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
// check if the list is empty
if (last == NULL) return NULL;
struct Node *newNode, *p;
p = last->next;
do {
// if the item is found, place newNode after it
if (p->data == item) {
// allocate memory to the new node
newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// make the next of the current node as the next of newNode
newNode->next = p->next;
// put newNode to the next of p
p->next = newNode;
// if p is the last node, make newNode as the last node
if (p == last) last = newNode;
return last;
}
p = p->next;
} while (p != last->next);
cout << "\nThe given node is not present in the list" << endl;
return last;
}
// delete a node
void deleteNode(Node** last, int key) {
// if linked list is empty
if (*last == NULL) return;
// if the list contains only a single node
if ((*last)->data == key && (*last)->next == *last) {
free(*last);
*last = NULL;
return;
}
Node *temp = *last, *d;
// if last is to be deleted
if ((*last)->data == key) {
// find the node before the last node
while (temp->next != *last) temp = temp->next;
// point temp node to the next of last i.e. first node
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
// travel to the node to be deleted
while (temp->next != *last && temp->next->data != key) {
temp = temp->next;
}
// if node to be deleted was found
if (temp->next->data == key) {
d = temp->next;
temp->next = d->next;
free(d);
}
}
void traverse(struct Node* last) {
struct Node* p;
if (last == NULL) {
cout << "The list is empty" << endl;
return;
}
p = last->next;
do {
cout << p->data << " ";
p = p->next;
} while (p != last->next);
}
int main() {
struct Node* last = NULL;
last = addToEmpty(last, 6);
last = addEnd(last, 8);
last = addFront(last, 2);
last = addAfter(last, 10, 2);
traverse(last);
deleteNode(&last, 8);
cout << endl;
traverse(last);
return 0;
}
In this example, a Circular Linked List is defined and put through a number of actions. With beginning nodes having the numbers 6, 8, 2, and 10 correspondingly, it constructs a circular linked list. The node with the value 8 is then deleted. The circular linked list's contents both before and after the deletion are printed as a final step.
Output:
2 6 10 8
2 6 10Applications of Circular Linked List
- This is used in multiplayer games to give each participant a chance to play.
- On an operating system, a circular linked list can be used to organize many running applications.
- The operating system iterates across these apps.
- In resource allocation difficulties, circular linked lists might be useful.
- Circular linked lists are frequently used to build circular buffers.
- They can also be used in simulation and gaming.
FAQs
1. What are the different types of circular linked lists?
There are two types of linked lists: singly circular linked lists, in which each node points to the next node, & doubly circular linked lists, in which each node also points to the previous node, allowing bidirectional traversal.
2. What is circular linked list with its application?
A circular linked list is a data structure in which the last node, forming a loop, points back to the first. It is utilised in applications such as circular buffers for efficient data storage, operating system process management, and circular navigation via playlists in media players.
3. What is circular linked list in data structure?
It is a data structure in which each node contains data as well as a reference (pointer) to the next node. The final node points to the first, forming a closed loop that allows for efficient circular traversal.
4. What is the difference between singly and doubly and circular linked lists?
Singly-linked lists have a single pointer to the next node, doubly linked lists have pointers to both the next and previous nodes, and circular linked lists form a loop by connecting the last node to the first.
5. Which is better circular or doubly linked list?
The decision is based on the unique use case. Circular linked lists use less memory and are better suited for circular traversal. Doubly linked lists provide bidirectional traversal but use more memory due to the extra preceding references.
6. What are the advantages of circular linked list?
They are memory-efficient for circular traversal applications, eliminating the need for a separate tail pointer, theoretically permit indefinite storage, and are appropriate for instances where elements form a closed-loop sequence.
Summary
Circular linked lists are an essential tool in modern programming, allowing for the efficient management of massive data sets and the solution of complex problems. While slightly more complicated than other lists, their adaptability makes them useful for a variety of jobs. Understanding circular linked list program in data structure, Circular linked list in data structures with example, circular linked list in data structure algorithm is advantageous, particularly for diverse coding platforms. Explore our website's resources to learn more and successfully address your programming challenges.
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
