Browse Articles

Circular Linked List in Data Structures

Amit Kumar Ghosh  34 min read
21 Sep 2023
Beginner
359 Views

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:

  1. Insertion
  2. 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 10

Applications 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.

Share
About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this