Circular Linked List | CrackEase

Circular Linked List

What is a circular linked list?

A Circular Linked List is a linked structure in which the last node points back to the first node, forming a circle. Each node typically contains a data value and a pointer to the next node. This structure is useful when you need to cycle through elements repeatedly.

Why use a circular linked list?

Use circular linked lists when you need to repeatedly loop through elements without restarting from the head explicitly. They are convenient for implementing round-robin schedulers and circular queues.

Advantages of circular linked list in C

Any node can act as the head since the list is circular.
Easy access to the first node from the last node; saves time in cyclic operations.
Useful for implementing queues and round-robin systems.

Code (Insertion at Beginning, End, After position)

  
// 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;

  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  last = newNode;
  last->next = last; // link to itself
  return last;
}

struct Node* addFront(struct Node* last, int data) {
  if (last == NULL) return addToEmpty(last, data);
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = last->next;
  last->next = newNode; // newNode becomes first node
  return last;
}

struct Node* addEnd(struct Node* last, int data) {
  if (last == NULL) return addToEmpty(last, data);
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = last->next;
  last->next = newNode;
  last = newNode;
  return last;
}

struct Node* addAfter(struct Node* last, int data, int item) {
  if (last == NULL) return NULL;
  struct Node *newNode, *p;
  p = last->next;
  do {
    if (p->data == item) {
      newNode = (struct Node*)malloc(sizeof(struct Node));
      newNode->data = data;
      newNode->next = p->next;
      p->next = newNode;
      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;
}

void deleteNode(struct Node** last, int key) {
  if (*last == NULL) return;

  if ((*last)->data == key && (*last)->next == *last) {
    free(*last);
    *last = NULL;
    return;
  }

  struct Node *temp = *last, *d;

  if ((*last)->data == key) {
    while (temp->next != *last) temp = temp->next;
    temp->next = (*last)->next;
    free(*last);
    *last = temp->next;
    return;
  }

  while (temp->next != *last && temp->next->data != key) temp = temp->next;
  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>
#include <cstdlib>
using namespace std;

struct Node {
  int data;
  struct Node* next;
};

struct Node* addToEmpty(struct Node* last, int data) {
  if (last != NULL) return last;
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  last = newNode;
  last->next = last;
  return last;
}

struct Node* addFront(struct Node* last, int data) {
  if (last == NULL) return addToEmpty(last, data);
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = last->next;
  last->next = newNode;
  return last;
}

struct Node* addEnd(struct Node* last, int data) {
  if (last == NULL) return addToEmpty(last, data);
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = last->next;
  last->next = newNode;
  last = newNode;
  return last;
}

struct Node* addAfter(struct Node* last, int data, int item) {
  if (last == NULL) return NULL;
  struct Node *newNode, *p;
  p = last->next;
  do {
    if (p->data == item) {
      newNode = (struct Node*)malloc(sizeof(struct Node));
      newNode->data = data;
      newNode->next = p->next;
      p->next = newNode;
      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;
}

void deleteNode(Node** last, int key) {
  if (*last == NULL) return;
  if ((*last)->data == key && (*last)->next == *last) {
    free(*last);
    *last = NULL;
    return;
  }
  Node *temp = *last, *d;
  if ((*last)->data == key) {
    while (temp->next != *last) temp = temp->next;
    temp->next = (*last)->next;
    free(*last);
    *last = temp->next;
    return;
  }
  while (temp->next != *last && temp->next->data != key) temp = temp->next;
  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;
    Node newNode = new Node();
    newNode.data = data;
    last = newNode;
    newNode.next = last;
    return last;
  }

  static Node addFront(Node last, int data) {
    if (last == null) return addToEmpty(last, data);
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = last.next;
    last.next = newNode;
    return last;
  }

  static Node addEnd(Node last, int data) {
    if (last == null) return addToEmpty(last, data);
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = last.next;
    last.next = newNode;
    last = newNode;
    return last;
  }

  static Node addAfter(Node last, int data, int item) {
    if (last == null) return null;
    Node p = last.next;
    do {
      if (p.data == item) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = p.next;
        p.next = newNode;
        if (p == last) last = newNode;
        return last;
      }
      p = p.next;
    } while (p != last.next);
    System.out.println("The given node is not present in the list");
    return last;
  }

  static Node deleteNode(Node last, int key) {
    if (last == null) return null;
    if (last.data == key && last.next == last) { return null; }
    Node temp = last;
    if (last.data == key) {
      while (temp.next != last) temp = temp.next;
      temp.next = last.next;
      last = temp.next;
      return last;
    }
    while (temp.next != last && temp.next.data != key) temp = temp.next;
    if (temp.next.data == key) temp.next = temp.next.next;
    return last;
  }

  static void traverse(Node last) {
    if (last == null) { System.out.println("List is empty."); return; }
    Node 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);
    last = deleteNode(last, 67);
    System.out.println();
    traverse(last);
  }
}

	
12 90 67 10 
12 90 10

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Circular Linked List

What is a circular linked list?