A Circular Linked List is a collection of elements connected together with the help of pointers. Such that each node contains a data value and addresses to the next node in the link. Where the last link of the circular Linked list has the address of the first node.
As we know that singly linked list and doubly linked list are already present in there in data structure and algorithm then what is the need of circular linked list?
When we want to access the things in a loop repeatedly. Circular Linked List is ideal so that, whenever we reach the last node we can restart operations again by directly reaching the first node from the last node itself.
// C code to perform circular linked list operations
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data) {
if (last != NULL) return last;
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to the new node
newNode->data = data;
// assign last to newNode
last = newNode;
// create link to iteself
last->next = last;
return last;
}
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the current first node in the newNode
newNode->next = last->next;
// make newNode as head
last->next = newNode;
return last;
}
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the head node to next of newNode
newNode->next = last->next;
// point the current last node to the newNode
last->next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
// check if the list is empty
if (last == NULL) return NULL;
struct Node *newNode, *p;
p = last->next;
do {
// if the item is found, place newNode after it
if (p->data == item) {
// allocate memory to the new node
newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// make the next of the current node as the next of newNode
newNode->next = p->next;
// put newNode to the next of p
p->next = newNode;
// if p is the last node, make newNode as the last node
if (p == last) last = newNode;
return last;
}
p = p->next;
} while (p != last->next);
printf("\nThe given node is not present in the list");
return last;
}
// delete a node
void deleteNode(struct Node** last, int key) {
// if linked list is empty
if (*last == NULL) return;
// if the list contains only a single node
if ((*last)->data == key && (*last)->next == *last) {
free(*last);
*last = NULL;
return;
}
struct Node *temp = *last, *d;
// if last is to be deleted
if ((*last)->data == key) {
// find the node before the last node
while (temp->next != *last) temp = temp->next;
// point temp node to the next of last i.e. first node
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
// travel to the node to be deleted
while (temp->next != *last && temp->next->data != key) {
temp = temp->next;
}
// if node to be deleted was found
if (temp->next->data == key) {
d = temp->next;
temp->next = d->next;
free(d);
}
}
void traverse(struct Node* last) {
struct Node* p;
if (last == NULL) {
printf("The list is empty");
return;
}
p = last->next;
do {
printf("%d ", p->data);
p = p->next;
} while (p != last->next);
}
int main() {
struct Node* last = NULL;
last = addToEmpty(last, 90);
last = addEnd(last, 67);
last = addFront(last, 12);
last = addAfter(last, 10, 67);
traverse(last);
deleteNode(&last, 67);
printf("\n");
traverse(last);
return 0;
}
// C++ code to perform circular linked list operations
#include<iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data) {
if (last != NULL) return last;
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to the new node
newNode->data = data;
// assign last to newNode
last = newNode;
// create link to iteself
last->next = last;
return last;
}
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the current first node in the newNode
newNode->next = last->next;
// make newNode as head
last->next = newNode;
return last;
}
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);
// allocate memory to the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// store the address of the head node to next of newNode
newNode->next = last->next;
// point the current last node to the newNode
last->next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
// check if the list is empty
if (last == NULL) return NULL;
struct Node *newNode, *p;
p = last->next;
do {
// if the item is found, place newNode after it
if (p->data == item) {
// allocate memory to the new node
newNode = (struct Node*)malloc(sizeof(struct Node));
// add data to the node
newNode->data = data;
// make the next of the current node as the next of newNode
newNode->next = p->next;
// put newNode to the next of p
p->next = newNode;
// if p is the last node, make newNode as the last node
if (p == last) last = newNode;
return last;
}
p = p->next;
} while (p != last->next);
cout << "\nThe given node is not present in the list" << endl;
return last;
}
// delete a node
void deleteNode(Node** last, int key) {
// if linked list is empty
if (*last == NULL) return;
// if the list contains only a single node
if ((*last)->data == key && (*last)->next == *last) {
free(*last);
*last = NULL;
return;
}
Node *temp = *last, *d;
// if last is to be deleted
if ((*last)->data == key) {
// find the node before the last node
while (temp->next != *last) temp = temp->next;
// point temp node to the next of last i.e. first node
temp->next = (*last)->next;
free(*last);
*last = temp->next;
}
// travel to the node to be deleted
while (temp->next != *last && temp->next->data != key) {
temp = temp->next;
}
// if node to be deleted was found
if (temp->next->data == key) {
d = temp->next;
temp->next = d->next;
free(d);
}
}
void traverse(struct Node* last) {
struct Node* p;
if (last == NULL) {
cout << "The list is empty" << endl;
return;
}
p = last->next;
do {
cout << p->data << " ";
p = p->next;
} while (p != last->next);
}
int main() {
struct Node* last = NULL;
last = addToEmpty(last, 90);
last = addEnd(last, 67);
last = addFront(last, 12);
last = addAfter(last, 10, 67);
traverse(last);
deleteNode(&last, 67);
cout << endl;
traverse(last);
return 0;
}
// Java code to perform circular linked list operations
class CircularLinkedList {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node last, int data) {
if (last != null)
return last;
// allocate memory to the new node
Node newNode = new Node();
// assign data to the new node
newNode.data = data;
// assign last to newNode
last = newNode;
// create link to iteself
newNode.next = last;
return last;
}
// add node to the front
static Node addFront(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the current first node in the newNode
newNode.next = last.next;
// make newNode as head
last.next = newNode;
return last;
}
// add node to the end
static Node addEnd(Node last, int data) {
if (last == null)
return addToEmpty(last, data);
// allocate memory to the new node
Node newNode = new Node();
// add data to the node
newNode.data = data;
// store the address of the head node to next of newNode
newNode.next = last.next;
// point the current last node to the newNode
last.next = newNode;
// make newNode as the last node
last = newNode;
return last;
}
static Node addAfter(Node last, int data, int item) {
if (last == null)
return null;
Node newNode, p;
p = last.next;
do {
// if the item is found, place newNode after it
if (p.data == item) {
// allocate memory to the new node
newNode = new Node();
// add data to the node
newNode.data = data;
// make the next of the current node as the next of newNode
newNode.next = p.next;
// put newNode to the next of p
p.next = newNode;
// if p is the last node, make newNode as the last node
if (p == last)
last = newNode;
return last;
}
p = p.next;
} while (p != last.next);
System.out.println(item + "The given node is not present in the list");
return last;
}
// delete a node
static Node deleteNode(Node last, int key) {
// if linked list is empty
if (last == null)
return null;
// if the list contains only a single node
if (last.data == key && last.next == last) {
last = null;
return last;
}
Node temp = last, d = new Node();
// if last is to be deleted
if (last.data == key) {
// find the node before the last node
while (temp.next != last) {
temp = temp.next;
}
// point temp node to the next of last i.e. first node
temp.next = last.next;
last = temp.next;
}
// travel to the node to be deleted
while (temp.next != last && temp.next.data != key) {
temp = temp.next;
}
// if node to be deleted was found
if (temp.next.data == key) {
d = temp.next;
temp.next = d.next;
}
return last;
}
static void traverse(Node last) {
Node p;
if (last == null) {
System.out.println("List is empty.");
return;
}
p = last.next;
do {
System.out.print(p.data + " ");
p = p.next;
}
while (p != last.next);
}
public static void main(String[] args) {
Node last = null;
last = addToEmpty(last, 90);
last = addEnd(last, 67);
last = addFront(last, 12);
last = addAfter(last, 10, 67);
traverse(last);
deleteNode(last, 67);
System.out.println();
traverse(last);
}
}
12 90 67 10
12 90 10