Circular Linked List with C++ Code Implementation

A linked list (singly or doubly) in which starting from a given node we can reach all the nodes and come back to the node where we started i.e a linked list in which all nodes form a circle is called a circular linked list.

A Pictorial Representation :


A circular linked list has the following operations associated with it:
  1. Insertion in an empty linked list
  2. Insertion at the beginning of the list
  3. insertion at end of the list
  4. insertion between the list
These operation can be performed in the same way in which we have done for single linked list or double linked list.

Here we will take a head pointer to point to the starting of our list, various operations associated with the circular linked list are shown in the code

  • Video Explanation:

C++ Code Implementation


#include <bits/stdc++.h>

void insertempty(int x);
void insertend(int x);
void insertbeg(int x);
void print(struct node *temp);
void insertbetween(int x, int pos);

using namespace std;

struct node {
int data;
struct node *next; // pointer to point the address of
        // next node
} *head = NULL; // to point to the first node of
        // linked list

int main() {
insertempty(10);
insertend(30);
insertbeg(20);
insertbetween(50, 2);
insertbetween(22, 2);
print(head);
return 0;
}

void insertempty(int x) {
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
nnode->data = x;
if (head == NULL) {
head = nnode;
nnode->next = nnode;
}
}

void insertend(int x) {
struct node *temp;
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
nnode->data = x;
temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = nnode;
nnode->next = head;
}

void insertbeg(int x) {
struct node *temp;
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
nnode->data = x;
temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = nnode;
nnode->next = head;
head = nnode;
}

void insertbetween(int x, int pos) {
struct node *temp;
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
nnode->data = x;
temp = head;
int i = 1;
while (i != pos - 1) {
temp = temp->next;
i++;
}
nnode->next = temp->next;
temp->next = nnode;
}

void print(struct node *temp) {
while (temp->next != head) {
cout << temp->data << endl;
temp = temp->next;
}
cout << temp->data << endl;
}

Output:


20
22
50
10
30

Problems :

  1. Cycle Detection
  2. Remove Friends ( HackerEarth )
  3. Reversed Linked List ( HackerEarth )

We use a circular linked list whenever we have to go through the data of the list repeatedly such as an operating system using a list to do a set of operations by CPU.

If there is an error or want to discuss your approach, then please feel free to drop in the comment section.

Thank You for Reading

Related Posts



If you like Learn DSA and would like to contribute please mail your article to info.learndsa@gmail.com and see your article appearing on the Learn DSA main page and help other.