A linked list is a common data structure made of a chain of nodes where each node contains a value and a pointer to the next node in the chain.
The head pointer points to the first node, and the last element of the list points to null
. When the list is empty, the head pointer points to null
.
A circular linked list is a variation of a normal linked list. In a circular linked list, as the name suggests, the list does not end; instead, it loops around. The last element of a circular linked list points to the head instead of pointing to null
. A circular linked list can be implemented as a
There are three fundamental operations that every linked list does:
Here is an example that implements each of the three operations:
#include "Clinkedlist.h"circularLinkedList::circularLinkedList(){head = NULL;}bool circularLinkedList::addElement(int element){//creating nodenode* newNode = new node;newNode->data = element;newNode->next = NULL;//first elementif (!head){head = newNode;head->next = newNode;return true;}//variable to find end of linked listnode* dummy = head;//finding last element of linked listdo{//ensures that same element is not added twiceif (dummy->data == element){return false;}dummy = dummy->next;} while (dummy->next != head);dummy->next = newNode;newNode->next = head;return true;}bool circularLinkedList::deleteElement(int element){//if list is emptyif (!head){return false;}//variables to find the element to deletenode* prev_dummy = head;node* curr_dummy = head->next;if(prev_dummy == curr_dummy){if (curr_dummy->data == element){delete head;head = NULL;return true;}return false;}do{//deleting dataif(curr_dummy->data == element){if (curr_dummy == head){head = curr_dummy->next;}prev_dummy->next = curr_dummy->next;delete curr_dummy;return true;}prev_dummy = prev_dummy->next;curr_dummy = curr_dummy->next;} while (prev_dummy != head);return false;}void circularLinkedList::display(){//variable to traverse linked listnode* dummy = head;do{std::cout << "data: " << dummy->data << endl;dummy = dummy->next;} while (dummy!= head);}
There are two things to be careful of when writing the addElement()
function for a ​circular linked list:
head
of the linked list equal to newNode
. next
should point to itself.next
pointer of the last node point to newNode
and the next pointer of newNode
point to head
.When deleting an element, you need to be mindful of two things:
head
pointer to Null
.next
point to the current node’s next
. Then delete the current node.Displaying the data of a circular linked list is similar to a normal linked list – you visit each node and print the data.
The only difference between the two lists is in the method of termination. When printing data of a normal linked list, the code should start displaying data from the head
pointer and terminate as soon as null
is hit. Whereas, in a circular linked list, the code should start displaying data from the head
pointer and terminate as soon as head
is reached again.
Free Resources