Circular Linked List in C++

Introduction to Circular Linked List In C++

As we know, the linked list is a linear data structure which is consist of a node and each node may hold some value and address of another node. As memory allocated to the nodes is done at runtime means memory blocks are non-contiguous which makes the direct access of the nodes hard and done by traversing over the linked list. For a singly or doubly linked list if we have to traverse from the last node to the first node or if we have to change the head of the linked list then it will be very costly in terms of time, for this we have a solution that is the circular linked list in which the last node contains the address of the first node which makes the singly linked list circular linked list and every node can be treated as the head node.

Structure of Circular Linked List in C++

The structure of the circular linked list is exactly similar to the structure of the singly linked list. It will contain two variables first one is of primitive or user-defined data type to store the data at the current node and another is a pointer to store the reference or address of the next node.

The above structure of the circularly linked list is declared using the struct keyword and contains a variable to store the data which could be any data type or data structure according to the need or program. In the end, there is a pointer that will keep the address of the next node.

Declaration

Well, creating the structure of the circular linked list is one type of declaration. In C++ we have two options present to create a user-defined data type that is structures and classes. In the above section, we have seen the structure for the declaration of the circular linked list, now let’s declare it by using classes:

Above class declaration, for the circular linked list is mostly equal to structure one, the only difference of the keyword is 'class' now instead of struct and access specifiers. Structures don’t provide the facility to initialize the data with the declaration of the structure while in class we can initialize declared variables that escape them from storing garbage values. One more function provided by the classes over the structure is constructors by which users easily initialize the variables. Let’s see the declaration of a circular linked list with the class which will consist of different types of constructors:

In the above syntax, first, we declared a class that consists of two variables, and both are initialized with respected values. After that, we created a constructor by which the user can initialize data with the required value.

Program to Implement Circular Linked List

We have seen how to declare a structure or class for the circular linked list, now let’s see a program in which we create a circular linked list by creating nodes manually and linking them:

Example:

Output:

Explanation: In the above code, first, we have created the class to provide the structure for nodes. Then in the main function by using the new() function of C++ we allocated the memory and by using the constructor of the Node class we created a node and stored its reference in the ‘first’ pointer. Similarly, we created ‘second’, and ‘third’, and instead of ‘fourth’ to give better visualization, we created the ‘last’ pointer and each of them contains the 1,2,3, and 4 as data values and NULL as a pointer reference. Then we manually linked each of them and to create a ‘circular’ linked list we linked the last node to the first by adding the reference of the ‘first’ node to the next or the last node. To show the circular linked list we printed the cycle by taking reference of the first node and forwarded it 9 times using the while loop.

How Circular Linked List Works in C++? (with Codes, Complexity, and Explanation for Each)

In the above section, we have seen how to create a circular linked list but here is one thing, we were creating every node manually and joining or linking every node manually. There are various operations we can perform on a circular linked list like insertion, deletion, and traversal. To keep the address of the linked list we will create a global pointer, let's say ‘head’, and initially, it will contain ‘NULL’.

1. Insertion

Insertion means to add a new node in the circular linked list, so first, we have to create the new node for insertion:

There are three possible positions to insert a new node in the circular linked list:

Insertion in an Empty List

Inserting in an empty circular linked list means creating a new list. In this case, we are going to create a new node and will store the address of the same node at the place of the next node. Also, the list is empty means our head pointer will contain the ‘NULL’ value.

In the above code, we first checked whether the list is empty or not by checking head is 'NULL' or not. Then assigned the head reference of new_node and to make it circular added a reference of head to head's next. Time Complexity: Time complexity for insertion in an empty list is O(1).

Insertion at the Beginning of the List

For inserting a new node at the beginning, we have to do three operations:

• Assigning reference of head to the next pointer of the new node.
• As a new node is going to be the head of the circular list, we will assign the head a new reference which is the address of the new node.
• Now we have a new first node so, in the last node, we have to update the address of the next node.

In the above code, first, we assigned a reference of the head pointer to the next new node, then update the head, and at last updated the value of the head in the last node to do so, we first found the last node by finding node which will contain the next pointer as our previous head or current head’s next. Time Complexity: Time complexity for insertion at beginning of list is O(N), where N is the number of nodes.

Insertion at the End of the List

For inserting a new node at the end of the list, we have to do two operations:

• Assigning reference of head to the next pointer of the new node, as the new node is going to be the last node so its next node will be the head or first node.
• For our previous last node, now the next node is a new node so we will update the previous last node's next pointer value.

In the above code, first, we assigned the head to the next pointer of the new node and then got the last node by using the while loop. In the end, we have assigned the new node to the next pointer of the previous node.

Time Complexity: The time complexity for insertion at end of the list is O(N), where N is the number of nodes.

Insertion in Between the Nodes

For inserting a new node between two nodes, we are provided with two nodes let's say first and second, we have to do two operations to add a new node between them:

• Assigning reference of the new node to the next pointer of the first node, as the new node will be the next node.
• Assigning reference of the new second node to the next pointer of the new node.

In the above code, first, we assigned a new_node reference to the next of the first node and then the second node as the next node of the new node.

Time Complexity: Time complexity for insertion in between two nodes is O(1).

2.Deletion

As the name suggests, deletion means to delete a node. Before we discuss possible positions for deletion let’s talk about the term memory leak. Linked lists or circular linked lists are created using dynamic memory allocation and allocated memory only deallocates when the program ends or the user manually deletes it using the delete function of C++. If the user forgets to manually deallocates the memory then it may arise the problem of a memory leak where the program terminates due to lack of memory. To prevent this problem use the delete() function to deallocate out-of-use memory blocks. Now, let’s see the three different types of possible locations from where the user may delete the node:

Deletion at the Beginning of the List

For the deletion of the node at the beginning, we have to do three operations:

• Assigning reference of head to the next pointer of the head itself.
• As the second node is going to be the head of the circular list, we will update the address of the next node.
• Finally, we will delete the previous head pointer.

In the above code, first, we have assigned a reference of the head pointer to the next of the head itself and stored the previous first node’s reference in the temporary pointer to de-allocate it by using the delete function. At last update the value of the next pointer of the last node with the new head.

Time Complexity: Time complexity of deletion at beginning of the list is O(N), where N is the number of nodes.

Deletion at the end of the list

For the deletion of the node at the end, we have to do two operations:

• Assigning reference of head to the second last node because this is going to be the last node after deletion.
• Finally, we will delete the previous last pointer.

In the above code, first, we found the address of the second last node, then delete the last node by using the second last node's next pointer, and then updated the second last node's next pointer to store the head as it is now the last node.

Time Complexity: Time complexity of deletion at beginning of the list is O(N), where N is the number of nodes.

Deletion in Between the Nodes

For deleting a node between two nodes, we are provided with two nodes let's say first and second, we have to do two operations to delete a node between them:

• Deallocating the memory of the node next to the first node.
• Assigning reference of the second node to the next pointer of the first node, as the middle node is deleted. e.

In the above code, first, we deallocated the node to be deleted and then assigned the second node as the next node of the first.

Time Complexity: Time complexity for insertion in between two nodes is O(1).

3. Traversal

Traversal for a circular linked list means visiting over the nodes and for this, we only need a single pointer which is the head or any node of the circular linked list.

As the whole list is connected to each other in the cycle which means we can visit every node and can get back to the starting point. Let’s see this using example:

In the above code, we created a temporary variable and assigned it the value of head. Using the while loop we keep updating the temp with it next until we reach the last node in that case next pointer will be equal to the head.

Time Complexity: Time complexity for traversal of circular linked list is O(N).

Advantages and Disadvantages of Circular Linked List in C++

Advantages:

There are many advantages of the circular linked list, let’s see some of them:

• In a circular linked list, the last node is connected to the first one which makes circular operations like scheduling easy.
• Every node can be considered as a head node or first node which makes traversal over the list easy.
• There is no need to initialize the next pointer with a NULL value as there will always be an option for the next node.
• It reduces the time complexity for many operations in some advanced data structures.
• Scheduling algorithms like Round Robing can be set up without worrying about NULL pointer reference.

Disadvantages:

There are many advantages of the circular linked list but there are some demerits also, let’s see some disadvantages of them:

• A circular linked list must be handled properly otherwise there is a huge possibility to stuck in an infinite loop.
• As the memory blocks are discontinuous, the user cannot directly access the elements.
• Reversing a circular linked list is hard as compared to a singly linked list. Also, managing the circular linked list is hard compared to both singly and doubly linked lists.

Applications of Circular Linked List in C++

There are many real-life applications of the circular linked list and to create many complex data structures circular linked list is used. Let’s see some of them:

• Circular linked lists are used by the operating system to manage computer resources. Also, many times in the scheduling circular linked list is used.
• In computer networks, the circular linked list is used in token scheduling.
• Many advanced data structures are implemented using the circular linked list like Fibonacci Heap is implemented using circular linked list.
• Data structures queue and stack can also be implemented using it.