Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

circular
linked list

What is a circular linked list?

Educative Answers Team
svg viewer

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:

  1. Add element
  2. Delete element
  3. 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);
}

1. Add element

There are two things to be careful of when writing the addElement() function for a ​circular linked list:

  1. When adding an element to an empty list, make head of the linked list equal to newNode. next should point to itself.
  2. When adding an element to a linked list with one or more nodes, you need to find the last element before it loops to head again. Then, make the next pointer of the last node point to newNode and the next pointer of newNode point to head.
svg viewer
svg viewer

2. Delete element

When deleting an element, you need to be mindful of two things:

  1. When you are deleting an element from a circular linked list of size one, you need to point the head pointer to Null.
  2. When you are deleting an element from a list with two or more elements, you need to keep track of two pointers: current and previous. As soon as the current reaches the target node, make the previous node’s next point to the current node’s next. Then delete the current node.

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.

svg viewer

RELATED TAGS

circular
linked list
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring