Breaking into the programming world might be slightly more difficult than expected. If one wants to make it to a product-based software company in the future, knowledge of data structures and algorithms is essential. In our day-to-day lives, we use a variety of different data structures. One of the most popular data structures used throughout the world of computer science is the linked list.
A linked list has many problems on its own, however. One needs to store a pointer to the head of the linked list carefully somewhere and store its value inside another pointer before manipulating the linked list. To resolve this issue, we use two slightly modified versions of the linked list: the doubly linked list and the circular linked list. In this article, we would be having a look at the implementation of circular singular linked list in C++ and the various operations such as insertion and deletion that can be performed on it, learn them from scratch. We included complete C++ program code for a circular linked list.
What is a Circular Linked List?
A circular linked list is a linked list where all nodes are connected to form a circle. Generally, the last node of the linked list has a NULL in the address field, but a circular linked list has the address of the head node in the address field of the last node. If you are not up-to-date with what a linked list is; it is a data structure that allows allocation of memory dynamically (that is, depending on our needs). It is made up of nodes that have two main components:
- Some data inside it. It can be a combination of many data types or a single data type.
- A pointer to the next node in the linked list.
A linked list starts with a head node – the first node in the list. Nodes are appended one by one to the list starting from the head.
C++ Implementation for Circular Linked List
The circular linked list consists of several operations that can be performed on it. We are including an implementation of the circular linked list in C++ with the various functionalities such as insertion and deletion that should come with it. Following is the complete code of the circular linked list in C++.
#include<bits/stdc++.h> using namespace std; struct Node { int data; //data of the node struct Node *next; //pointer to the next node in the list }; int Length(struct Node *head) //function to calculate the length of the linked list { struct Node *t; int i = 0; if (head == NULL) //handle underflow condition { return 0; } t = head -> next; do { //handle traversal through the list t = t -> next; i++; } while (t != head->next); return i; } struct Node *Start(struct Node *head, int data) //function to insert nodes at the beginning of the list { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)); if (head == NULL) //handle underflow condition { temp -> data = data; head = temp; head -> next = head; } else { temp -> data = data; temp -> next = head -> next; head -> next = temp; head = temp; } return head; } struct Node *End(struct Node *head, int data) //function to insert nodes at the end of the list { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)), *a = head; if (head == NULL) //handle underflow condition { temp -> data = data; head = temp; head -> next = head; } else { do { a = a -> next; } while (a -> next != head); //traverse to the end of the list temp -> data = data; temp -> next = a -> next; a -> next = temp; } return head; } struct Node *Middle(struct Node *head, int data, int index) //function to insert nodes anywhere in between the beginning and the end { if (head == NULL) //handle underflow condition { cout << "List is empty!" << endl; return NULL; } int len = Length(head); //get the length of the list for making a decision if (index > len || index < 0) //wrong index given { cout << "Wrong input, insertion not possible!" << endl; return head; } if (index == 0) //insert at the beginning { head = Start(head,data); return head; } if (index == len) //insert at the end { head = End(head,data); return head; } struct Node *temp = (struct Node *)malloc(sizeof(struct Node)), *a = head; do { //handle data traversal from beginning to end a = a -> next; } while (a -> next != head); len = 0; while (1) { if (len == index) //handle node addition { temp -> data = data; temp -> next = a -> next; a -> next = temp; return head; } a = a -> next; len++; } } struct Node *First(struct Node* head) //function to delete node from the start of the list { struct Node *prev = head, *first = head; if (head == NULL) { //handle underflow condition cout << "List is empty" << endl; return NULL; } if (prev->next == prev) //handle deletion for only one node of the list { head = NULL; return head; } while (prev->next != head) { prev = prev->next; } prev->next = first->next; head = prev->next; free(first); return head; } struct Node *Last(struct Node* head) //function to delete node from the end of the list { struct Node *curr = head, *temp = head, *prev; if (head == NULL) { //handle underflow condition cout << "List is empty" << endl; return NULL; } if (curr->next == curr) //handle deletion for only one node of the list { head = NULL; return head; } while (curr->next != head) { prev = curr; curr = curr->next; } prev->next = curr->next; head = prev->next; free(curr); return head; } struct Node *Position(struct Node* head, int index) //function to delete data from anywhere in between the start and the end of the list { int len = Length(head); int count = 1; struct Node *prev = head, *next = head; if (head == NULL) { //handle underflow condition cout << "List is empty" << endl; return NULL; } if (index > len || index < 0) //wrong index entered { cout << "Wrong data given, deletion not possible!" << endl; return head; } if (index == 0) { First(head); return head; } if (index == len) { Last(head); return head; } while (len > 0) { //traverse through the list and delete the node in the list if (index == count) { prev->next = next->next; free(next); return head; } prev = prev->next; next = prev->next; len--; count++; } return head; } void Display(struct Node *head) //function to traverse throughout the list { struct Node *t; if (head == NULL) { cout << "Linked list is empty." << endl; return; } t = head; do { cout << t -> data << " -> "; t = t -> next; } while (t != head); cout<<" "<<endl; } int main() { struct Node *head = NULL; int n = 0,a = 0; char ch; while (1) { cout << " 1. Add at the beginning\n 2. Add at the end \n 3. Add at index \n 4. Display list \n 5. Remove from the start \n 6. Remove from the end \n 7. Remove from index \n 5. Quit" << endl; cin >> ch; switch (ch) { case '1' : cout << "Enter data" << endl; cin >> n; head = Start(head, n); break; case '2' : cout << "Enter data" << endl; cin >> n; head = End(head, n); break; case '3' : cout << "Enter data" << endl; cin >> n; cout << "Enter index to insert at" << endl; cin >> a; head = Middle(head, n, a); break; case '4' : Display(head); break; case '5' : head = First(head); break; case '6' : head = Last(head); break; case '7' : cout << "Enter index to insert at" << endl; cin >> a; head = Position(head,a); break; case '8' : exit(0); default : cout << "Wrong choice!" << endl; } } return 0; }
In a circular linked list, insertion can be done either at the beginning, at the end, or anywhere in between.
Insertion at the beginning
Unsurprisingly, because of the circular property, entering data at the beginning is slightly more complicated than entering data at the end. For entering data at the beginning of the linked list, we have to create a new node and assign the data to it. Once done, we have to traverse to the end of the linked list using a pointer.
Code:
struct Node *Start(struct Node *head, int data) { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)); if (head == NULL) { temp -> data = data; head = temp; head -> next = head; } else { temp -> data = data; temp -> next = head -> next; head -> next = temp; head = temp; } return head; } struct Node *Start(struct Node *head, int data) { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)); if (head == NULL) { temp -> data = data; head = temp; head -> next = head; } else { temp -> data = data; temp -> next = head -> next; head -> next = temp; head = temp; } return head; }
Insertion at the end
Entering data at the end is much easier than entering data at the beginning. Once again, we need to create a new node and assign the data to it. Following that, we need to traverse to the last node of the linked list.
Code:
struct Node *End(struct Node *head, int data) { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)), *a = head; if (head == NULL) { temp -> data = data; head = temp; head -> next = head; } else { do { a = a -> next; } while (a -> next != head); temp -> data = data; temp -> next = a -> next; a -> next = temp; } return head; }
Insertion at the middle
The fundamental algorithm for insertion is followed here for generalizing the use cases. Traverse the linked list till before the point where the new node has to be inserted.
Code:
struct Node *Middle(struct Node *head, int data, int index) { if (head == NULL) { cout << "List is empty!" << endl; return NULL; } int len = Length(head); if (index > len || index < 0) { cout << "Wrong input, insertion not possible!" << endl; return head; } if (index == 0) { head = Start(head,data); return head; } if (index == len) { head = End(head,data); return head; } struct Node *temp = (struct Node *)malloc(sizeof(struct Node)), *a = head; do { a = a -> next; } while (a -> next != head); len = 0; while (1) { if (len == index) { temp -> data = data; temp -> next = a -> next; a -> next = temp; return head; } a = a -> next; len++; } }
Similar to insertion, nodes can be deleted either from the beginning, from the end, or from anywhere in between. The only difference here is that one needs to check if the circular linked list is already empty before the deletion or not, which would mean an underflow has occurred, and a suitable error should be displayed.
Deletion of Element at Start
The process for deletion works almost in a similar manner as for insertion, with only one fundamental difference – deletion requires two pointers, one for pointing towards the node before, and one for pointing towards the node after. In a similar fashion as insertion, traverse till the last node of the linked list with one pointer and store the head of the linked list in another pointer.
Code:
struct Node *First(struct Node* head) { struct Node *prev = head, *first = head; if (head == NULL) { cout << "List is empty" << endl; return NULL; } if (prev->next == prev) { head = NULL; return head; } while (prev->next != head) { prev = prev->next; } prev->next = first->next; head = prev->next; free(first); return head; }
Deletion of Element at End
Deletion from the end is considerably easier. All you need to do is traverse till the end of the linked list with one pointer and till the node before the last node with another pointer.
Code:
struct Node *Last(struct Node* head) { struct Node *curr = head, *temp = head, *prev; if (head == NULL) { cout << "List is empty" << endl; return NULL; } if (curr->next == curr) { head = NULL; return head; } while (curr->next != head) { prev = curr; curr = curr->next; } prev->next = curr->next; head = prev->next; free(curr); return head; }
Deletion of Element at Middle
A generalized algorithm for deletion can be designed similarly to insertion. All one needs to do is make one pointer traverse to a node before the required node in the list and one pointer traverse to the required node itself.
Code:
struct Node *Position(struct Node* head, int index) { int len = Length(head); int count = 1; struct Node *prev = head, *next = head; if (head == NULL) { cout << "List is empty" << endl; return NULL; } if (index > len || index < 0) { cout << "Wrong data given, deletion not possible!" << endl; return head; } if (index == 0) { First(head); return head; } if (index == len) { Last(head); return head; } while (len > 0) { if (index == count) { prev->next = next->next; free(next); return head; } prev = prev->next; next = prev->next; len--; count++; } return head; }
Display Circular Linked List
Perhaps one of the simplest operations in case of any circular linked list is to print the value of the list. Store the value of the head of the list in a pointer, then traverse through the array till the next pointer of a node point towards the head of the list (that is the main condition for a circular linked list!).
Code:
void Display(struct Node *head) { struct Node *t; if (head == NULL) { cout << "Linked list is empty." << endl; return; } t = head; do { cout << t -> data << " -> "; t = t -> next; } while (t != head); cout<<" "<<endl; }
Advantages of Circular Linked-List
- There is no requirement of the NULL pointer in the circular linked-list
- End operations are well performed in a circular linked list as the beginning and endpoints are the same.
- Circular linked-list performs all the operations of singly linked-list properly.
- Any node in circular linked-list can be considered to be the starting point
- We can traverse to any node in the circular linked-list unlike linear linked-list
- Circular linked-list saves time when we have to travel from the first node to the last node
Disadvantages of Circular Linked-List
- The circular linked list is challenging to reverse.
- There are chances of occurring infinite loop while dealing with circular linked-list
- Suppose, in linear linked-list, and we want to visit the previous node. The operation is performed in a single step, but in a circular linked list, we have to complete the entire circle calling every node in such a scenario.
Applications of Circular Linked-List
- It is easy to implement the scheduling algorithm with the help of circular linked-list
- The circular linked list is used in token ring scheduling algorithms in computer networks.
- A circular linked list is used in display units that require the continuous traversal of the data.
- It is easy to implement queue and stack using circular linked-list
- A circular linked list is helpful to implement advanced data structures
- A circular linked-list is used in multiplayer games
- It is used in the browser cache that allows you to hit the BACK button
- A circular linked-list is used to perform the undo functionality in MS Word or Photoshop
- Circular linked-list uses the Most Recent List(MRU list)
Conclusion
That concludes our implementation of the circular linked list in C++, how to insert, delete and display nodes. A circular linked list is used in a variety of applications where flexibility is very important. A circular linked list can be used for the implementation of a circular queue and even more complicated data structures like a Fibonacci heap (one of its best uses in data structures, apparently). Circular linked lists are also used in a variety of practical real-world applications that works with the help of a queue.
