Circular Linked List

 

🔄 What is a Circular Linked List?

A Circular Linked List (CLL) is a variation of a linked list where the last node points back to the first node, forming a circular loop.

🧠 Key Points:

• There is no NULL at the end.

• It can be singly or doubly circular.

• In singly circular, each node has a pointer to the next node only.

• In doubly circular, each node has pointers to both next and previous nodes.

For this lesson, we’ll focus on Singly Circular Linked List.

---

🎯 Applications of Circular Linked List

• Circular queues

• Round-robin schedulers (e.g., CPU scheduling)

• Multiplayer games where turn rotation is needed

• Continuous loop playback of media

📘 Structure of a Node (Singly Circular)

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

In a CLL:

• If there is only one node, its next points to itself.

• In general, the last node's next points to the first node.

✅ Basic Operations in Circular Linked List

1. Insertion at the end

2. Insertion at the beginning

3. Deletion of a node

4. Display all nodes

✅ 1. Insert at the End

🧠 Idea:

• Create a new node.

• If list is empty, point new node to itself and make it head.

• Otherwise, traverse to the last node (node whose next is head), insert the new node after it, and update its next to head.

📋 Algorithm:

Algorithm InsertEnd(head, value):
1. Create newNode with data = value
2. If head == NULL:
     a. newNode.next = newNode
     b. head = newNode
3. Else:
     a. temp = head
     b. While temp.next != head:
           i. temp = temp.next
     c. temp.next = newNode
     d. newNode.next = head
4. Return head

---

✅ 2. Insert at the Beginning

🧠 Idea:

• Create a new node.

• If list is empty, point new node to itself and set as head.

• Else, traverse to last node, make last node point to new node, and new node point to head, then update head.

📋 Algorithm:

Algorithm InsertBeginning(head, value):
1. Create newNode with data = value
2. If head == NULL:
     a. newNode.next = newNode
     b. head = newNode
3. Else:
     a. temp = head
     b. While temp.next != head:
           i. temp = temp.next
     c. newNode.next = head
     d. temp.next = newNode
     e. head = newNode
4. Return head

---

✅ 3. Delete a Node (By Value)

🧠 Idea:

• Handle three cases:

  • List is empty.

  • Node to delete is head.

  • Node to delete is somewhere else.

• If node is found, update previous node's next pointer to skip the current node and free memory.

📋 Algorithm:

Algorithm DeleteNode(head, value):
1. If head == NULL:
     a. Print "Empty list"
     b. Return head
2. temp = head
3. If head.data == value:
     a. If head.next == head:
          i. Free head
          ii. head = NULL
     b. Else:
          i. last = head
          ii. While last.next != head:
                - last = last.next
          iii. last.next = head.next
          iv. Free head
          v. head = last.next
     c. Return head
4. prev = head
5. temp = head.next
6. While temp != head and temp.data != value:
     a. prev = temp
     b. temp = temp.next
7. If temp == head:
     a. Print "Value not found"
8. Else:
     a. prev.next = temp.next
     b. Free temp
9. Return head

---

✅ 4. Display the Circular Linked List

🧠 Idea:

• Start from head, keep printing until you circle back to head.

📋 Algorithm:

Algorithm Display(head):
1. If head == NULL:
     a. Print "List is empty"
     b. Return
2. temp = head
3. Do:
     a. Print temp.data
     b. temp = temp.next
   While temp != head

---

✅ 5. Check if List is Empty

Algorithm isEmpty(head):
1. Return (head == NULL)

🧑‍💻 C Code: Circular Linked List (Singly)
#include <stdio.h>
#include <stdlib.h>

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

struct Node* head = NULL;

// Function to insert at the end
void insertEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
    }
    printf("%d inserted at end\n", value);
}

// Function to insert at beginning
void insertBeginning(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        newNode->next = head;
        temp->next = newNode;
        head = newNode;
    }
    printf("%d inserted at beginning\n", value);
}

// Function to delete a node
void deleteNode(int value) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node *temp = head, *prev = NULL;

    // Case: head node to be deleted
    if (head->data == value) {
        while (temp->next != head)
            temp = temp->next;
        if (head == head->next) { // only one node
            free(head);
            head = NULL;
        } else {
            temp->next = head->next;
            free(head);
            head = temp->next;
        }
        printf("%d deleted from list\n", value);
        return;
    }

    // Case: non-head node to be deleted
    prev = head;
    temp = head->next;
    while (temp != head && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == head) {
        printf("Node not found\n");
    } else {
        prev->next = temp->next;
        free(temp);
        printf("%d deleted from list\n", value);
    }
}

// Function to display list
void display() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    printf("Circular Linked List: ");
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to head)\n");
}

// Menu-driven program
int main() {
    int choice, value;
    while (1) {
        printf("\n--- Circular Linked List Menu ---\n");
        printf("1. Insert at end\n");
        printf("2. Insert at beginning\n");
        printf("3. Delete node\n");
        printf("4. Display\n");
        printf("5. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                insertEnd(value);
                break;
            case 2:
                printf("Enter value: ");
                scanf("%d", &value);
                insertBeginning(value);
                break;
            case 3:
                printf("Enter value to delete: ");
                scanf("%d", &value);
                deleteNode(value);
                break;
            case 4:
                display();
                break;
            case 5:
                printf("Exiting...\n");
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}