Related Tags

circular

# What is a circular linked list?

## 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:

2. Delete element
3. Display list

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

main.cpp
#include "Clinkedlist.h"

{
}

{
//creating node
node* newNode = new node;
newNode->data = element;
newNode->next = NULL;

//first element
{
return true;
}

//variable to find end of linked list

//finding last element of linked list
do
{
//ensures that same element is not added twice
if (dummy->data == element)
{
return false;
}

dummy = dummy->next;

dummy->next = newNode;

return true;

}

{
//if list is empty
{
return false;
}

//variables to find the element to delete

if(prev_dummy == curr_dummy)
{
if (curr_dummy->data == element)
{
return true;
}
return false;
}

do
{
//deleting data
if(curr_dummy->data == element)
{
{
}
prev_dummy->next = curr_dummy->next;
delete curr_dummy;
return true;
}

prev_dummy = prev_dummy->next;
curr_dummy = curr_dummy->next;

return false;
}

{

do
{
std::cout << "data: " << dummy->data << endl;
dummy = dummy->next;
}


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.

### 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.

RELATED TAGS

circular