Chapter 6 - Circular Linked Lists

Chapter 6 – Circular Linked Lists

Leave a Comment | What is DSA? | By

Chapter 6: Circular Linked Lists

Welcome to Chapter 6! In this chapter, we will explore Circular Linked Lists, a variation of linked lists where the last node in the list points back to the first node, forming a circular structure. This type of linked list is particularly useful in scenarios where you need a continuous loop through your data.

What is a Circular Linked List?

A Circular Linked List is a type of linked list in which the last node points back to the first node instead of having a NULL pointer. This circular structure allows you to traverse the list from any node and return to the starting node without having to check for the end.

Here’s a graphical representation of a circular linked list:

[Data | Next] -> [Data | Next] -> [Data | Next] -+
   ^                                           |
   |                                           |
   +-------------------------------------------+

In this diagram, you can see that the next pointer of the last node points back to the first node, creating a loop.

Why Use Circular Linked Lists?

Circular linked lists are useful for scenarios that require a continuous loop or when you need to repeatedly cycle through the elements. Some applications include:

  • Round-Robin Scheduling: In operating systems, circular linked lists can be used to manage tasks in a round-robin fashion.
  • Circular Buffers: They are used in scenarios where you have a fixed-size buffer and need to overwrite old data when the buffer is full.
  • Navigation Systems: For continuous navigation without end, like in a continuous data feed.
See also  Introduction to DSA (Data Structures and Algorithms)

Just like how Emancipation Edutech Private Limited might use circular linked lists to cycle through learning modules or resources efficiently, these structures can simplify repetitive tasks.

Building a Circular Linked List

To implement a circular linked list, we start by defining the node structure:

#include <stdio.h>
#include <stdlib.h>

// Define a node structure
struct Node {
    int data;
    struct Node* next;
};

Creating a Node

Creating a node is similar to singly linked lists, but with an additional step to handle the circular nature:

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = newNode; // Point to itself initially
    return newNode;
}

Inserting Elements in a Circular Linked List

Here’s how you can insert nodes into a circular linked list:

  1. At the Beginning:

    void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
        return;
    }
    
    struct Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    newNode->next = *head;
    temp->next = newNode;
    *head = newNode;
}

    This function inserts a new node at the start of the circular list and adjusts the next pointers to maintain the circular structure.

  2. At the End:

    void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
        return;
    }
    
    struct Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

    This function adds a new node to the end of the circular list by traversing to the last node and updating pointers.

  3. Inserting After a Given Node:

    void insertAfter(struct Node* prevNode, int value) {
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL");
        return;
    }
    
    struct Node* newNode = createNode(value);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

    This function inserts a new node after a given node, adjusting the next pointers accordingly.

See also  Chapter 4 - Linked Lists

Traversing a Circular Linked List

Traversal in a circular linked list involves starting from the head and continuing until you return to the head:

void traverse(struct Node* head) {
    if (head == NULL) return;
    
    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to head)\n");
}

This function loops through the list and prints each node’s data until it returns to the head.

Example: Creating and Traversing a Circular Linked List

Here’s a sample program to create a circular linked list and traverse it:

int main() {
    struct Node* head = NULL;

    // Inserting nodes
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtBeginning(&head, 5);
    insertAtEnd(&head, 30);
    insertAfter(head->next, 15); // Insert 15 after the node with data 10

    // Traverse the list
    traverse(head);

    return 0;
}

Output:

5 -> 10 -> 15 -> 20 -> 30 -> (back to head)

Deleting Nodes in a Circular Linked List

Deleting nodes in a circular linked list involves similar steps as in singly linked lists but requires updating the next pointers to maintain the circular structure:

  1. Deleting the First Node:

    void deleteFirstNode(struct Node** head) {
    if (*head == NULL) return;
    
    struct Node* temp = *head;
    if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
        return;
    }
    
    struct Node* last = *head;
    while (last->next != *head) {
        last = last->next;
    }
    
    last->next = (*head)->next;
    *head = (*head)->next;
    free(temp);
}

  2. Deleting the Last Node:

    void deleteLastNode(struct Node** head) {
    if (*head == NULL) return;
    
    struct Node* temp = *head;
    if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
        return;
    }
    
    struct Node* prev = NULL;
    while (temp->next != *head) {
        prev = temp;
        temp = temp->next;
    }
    
    prev->next = *head;
    free(temp);
}

  3. Deleting a Node by Value:

    void deleteNodeByValue(struct Node** head, int value) {
    if (*head == NULL) return;
    
    struct Node* temp = *head;
    struct Node* prev = NULL;
    
    do {
        if (temp->data == value) {
            if (prev == NULL) { // Node to be deleted is the head
                deleteFirstNode(head);
                return;
            } else {
                prev->next = temp->next;
                free(temp);
                return;
            }
        }
        prev = temp;
        temp = temp->next;
    } while (temp != *head);
}

Advantages and Disadvantages of Circular Linked Lists

Advantages:

  • Circular Traversal: Easily traverse through the list without needing to check for the end.
  • Efficient for Round-Robin Scheduling: Ideal for scenarios where cyclic behavior is required.
See also  Chapter 5 - Doubly Linked Lists

Disadvantages:

  • Complexity: Slightly more complex to manage compared to singly linked lists.
  • Potential for Infinite Loops: If not handled carefully, circular traversal can lead to infinite loops.

Wrapping Up Chapter 6

In this chapter, we explored Circular Linked Lists, which offer continuous traversal and cyclic operations. Understanding circular linked lists enhances your ability to manage data in scenarios requiring repetitive processing or cyclic access.

Key takeaways:

  • Nodes in a circular linked list form a loop.
  • You can insert and delete nodes while maintaining the circular structure.
  • Traversing involves looping back to the starting point.

For additional practice and interactive examples, visit digilearn.cloud. Emancipation Edutech Private Limited encourages exploring different types of linked lists to deepen your understanding.

Next up: Stacks

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top