What is a circular linked list?

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 singly linked listcontains only next pointer or a doubly linked listcontains next and previous pointer.

There are three fundamental operations that every linked list does:

Add element
Delete element
Display list

Here is an example that implements each of the three operations:

main.cpp

Clinkedlist.cpp

Clinkedlist.h

#include "Clinkedlist.h"

circularLinkedList::circularLinkedList()
{
    head = NULL;
}

bool circularLinkedList::addElement(int element)
{
    //creating node
    node* newNode = new node;
    newNode->data = element;
    newNode->next = NULL;

    //first element
    if (!head)
    {
        head = newNode;
        head->next = newNode;
        return true;
    }

    //variable to find end of linked list
    node* dummy = head;

    //finding last element of linked list
    do
    {   
        //ensures that same element is not added twice
        if (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 empty
    if (!head)
    {
        return false;
    }

    //variables to find the element to delete
    node* 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 data
        if(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 list
    node* dummy = head;

    do
    {
        std::cout << "data: " << dummy->data << endl;
        dummy = dummy->next;
    } while (dummy!= head);
}

3. Display list

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.

What is a circular linked list?

What is a circular linked list?

1. Add element

2. Delete element

3. Display list