Circular linked list in Data Structure program

A circular linked list is used to loop your music playlist to implement a circular queue. A circular linked list is a unidirectional linked list; i.e., you can traverse it from head to tail. Unlike other linked lists, its tail points back at the head node. This tutorial will help you understand the fundamental technicalities of circular linked lists with all the necessary details and practical examples.

How to Implement a Circular Linked List?

You can create nodes of circular-linked lists using classes or structures. These nodes are then linked with each other using the next pointer.

Code:

//A c++ program to implement linked list

#include <bits/stdc++.h>

using namespace std;

//A class to create a node

class Node

{

public:

int data;

Node *next;

};

// a function to insert a node at the beginning

void push(Node **head, int data)

{

Node *newnode = new Node();

Node *temp = *head;

newnode->data = data;

newnode->next = *head;

//If linked list is not NULL then

//set the next of last node as newnode

if (*head != NULL)

{

while (temp->next != *head)

temp = temp->next;

temp->next = newnode;

}

else

newnode->next = newnode;

*head = newnode;//change head

}

//A function to print the linked list

void printList(Node *head)

{

Node *temp = head;

if (head != NULL)

{

do

{

cout << temp->data << " ";

temp = temp->next;

}

while (temp != head);

}

}

int main()

{

//we will start with empty list

Node *head = NULL;

// insert 12

push(&head, 12);//12->12

//insert 56

push(&head, 56);//56->12->56

//insert 2

push(&head, 2);//2->56->12->2

//Insert 11

push(&head, 11);//11->2->56->12->11

cout << "Created Linked List: \n ";

printList(head);

return 0;

}

Full Stack Web Developer Course

To become an expert in MEAN StackView Course

What Operations Can You Perform on a Circular Linked List?

You can perform two types of operations on this kind of linked list:

• Insertion
• Deletion

How to Insert a Node in a Circular Linked List?

To insert a node, you need to change the previous node's next (if any) to the new node and the new node next to the previous node's next. You can insert a new node in three different locations.

• At the beginning of the list
• At the end of the list
• After a given node

Code:

//A c++ program to perform insertion.

#include<bits/stdc++.h>

using namespace std;

//A structure to create nodes

struct Node

{

int data;

struct Node *next;

};

//A function to insert in the empty list

struct Node *addToEmpty(struct Node *last, int data)

{

// Check if list is empty

if (last != NULL)

return last;

// Creating a node dynamically.

struct Node *temp=(struct Node*)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;

last = temp;

// Creating the link.

last -> next = last;

return last;

}

//A function to insert at the beginning

struct Node *addBegin(struct Node *last, int data)

{

if (last == NULL)

return addToEmpty(last, data);

struct Node *temp=(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;

last -> next = temp;

return last;

}

//A function to insert at the end

struct Node *addEnd(struct Node *last, int data)

{

if (last == NULL)

return addToEmpty(last, data);

struct Node *temp =

(struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = last -> next;

last -> next = temp;

last = temp;

return last;

}

//A function to insert after the given node

struct Node *addAfter(struct Node *last, int data, int item)

{

if (last == NULL)

return NULL;

struct Node *temp, *p;

p = last -> next;

do

{

if (p ->data == item)

{

temp = (struct Node *)malloc(sizeof(struct Node));

temp -> data = data;

temp -> next = p -> next;

p -> next = temp;

if (p == last)

last = temp;

return last;

}

p = p -> next;

} while(p != last -> next);

cout << item << " not present in the list." << endl;

return last;

}

//A function to traverse and print the list

void traverse(struct Node *last)

{

struct Node *p;

// If the list is empty, return.

if (last == NULL)

{

cout << "List is empty." << endl;

return;

}

// Points to first node

p = last -> next;

// Traversing the list.

do

{

cout << p -> data << " ";

p = p -> next;

}

while(p != last->next);

}

int main()

{

//start with empty list

struct Node *head = NULL;

//insert 6 in empty list

head = addToEmpty(head, 6);//6->6

//insert 4 at the beginning

head = addBegin(head, 4);//4->6->4

//insert 2 at the beginning

head = addBegin(head, 2);//2->4->6->2

//insert 8 at the end

head = addEnd(head, 8);//2->4->6->8->2

//insert 12 at the end

head = addEnd(head, 12);//2->4->6->8->12->2

//insert 10 after 8

head = addAfter(head, 10, 8);//2->4->6->8->10->12->2

traverse(head);

return 0;

}

Add Another Star to Your Performance Evaluation

Learn from industry experts for FREEStart Learning

How to Remove a Node From a Circular Linked List?

You need to change the previous node's next to the deleted node's next to delete a node. You can delete a node from three different positions.

• From the beginning of the list
• From the end of the list
• After a given node

Code:

//A C++ program to delete a given key

#include <bits/stdc++.h>

using namespace std;

// A class to create node

class Node {

public:

int data;

Node* next;

};

//A function to insert at the beginning

void push(Node** head, int data)

{

// Creating a newnode and make its next as head

Node* newnode = new Node();

newnode->data = data;

newnode->next = *head;

//If linked list is not empty

if (*head!= NULL)

{

// Find the node before head and update

// next to it.

Node* temp = *head;

while (temp->next != *head)

temp = temp->next;

temp->next = newnode;

}

else

newnode->next = newnode;

*head = newnode;

}

//A function to print the list

void printList(Node* head)

{

Node* temp = head;

if (head != NULL) {

do {

cout << temp->data << " ";

temp = temp->next;

} while (temp != head);

}

cout << endl;

}

//A Function to delete a given node

void deleteNode(Node** headref, int key)

{

// If linked list is empty

if (*headref == NULL)

return;

// If the list has single node

if((*headref)->data==key && (*headref)->next==*headref)

{

free(*headref);

*headref=NULL;

return;

}

Node *last=*headref,*d;

// If the key is headref itself

if((*headref)->data==key)

{

// Find the last node of the list

while(last->next!=*headref)

last=last->next;

// Point last node to the next of headref i.e.

// the second node of the list

last->next=(*headref)->next;

free(*headref);

*headref=last->next;

}

//if key not found or end of the list not reached

while(last->next!=*headref && last->next->data!=key)

{

last=last->next;

}

// If node to be deleted was found

if(last->next->data==key)

{

d=last->next;

last->next=d->next;

free(d);

}

else

cout<<"no such key found";

}

/* Driver code */

int main()

{

// we will start list empty

Node* head = NULL;

//Created linked list will be 2->5->7->8->10

push(&head, 2);

push(&head, 5);

push(&head, 7);

push(&head, 8);

push(&head, 10);

cout << "List Before Deletion: ";

printList(head);

deleteNode(&head, 7);//delete 7

cout << "List After Deletion: ";

printList(head);

return 0;

}

What Are the Benefits of a Circular Linked List?

• You can traverse to any node from any node.
• It is faster to traverse from the last node to the first node.
• The circular linked list is beneficial in applications that require looping.
• You can implement complex data structures like circular queues.

What Are the Limitations of a Circular Linked List?

• It is hard to reverse traverse a circular linked list.
• While traversing, if not careful, you can end up in an infinite loop.
• Similar to singly linked lists and doubly linked lists, you can't directly access any element of the linked lists.

Advance your career as a MEAN stack developer with theFull Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

"Stacks in data structure" will be your next stop. Stacks are nodes that are piled on one another. You can perform operations only on the top node. Stacks can be used to backtrack to the previous installation or to solve complex problems like N-Queens.

If you are perhaps looking to build a career in software development, explore Simplilearns Software Development Courses that will give you the work-ready software development training you need to succeed today.

If you have any questions about this article, please feel free to leave them in the comment section below. Our expert team is available 24/7 to answer all your queries for you at the earliest.

Happy learning!