Circular Linked Lists: One Step at a Time!

Before starting this tutorial, make sure to check out Linked Lists: One Step at a Time! to understand the basics of singly linked lists first.

First Step: What is a Circular Linked List?

Explanation:

• A circular linked list is similar to a singly linked list, but with one key difference.

• The last node's next pointer points back to the first node instead of NULL.

• This creates a circular structure with no beginning or end.

• We often keep a pointer to the last node (tail) for efficient operations.

• The node structure is the same as a singly linked list.

Code:

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

// Define the node structure (same as singly linked list)
struct Node {
    int data;           // Integer data
    struct Node* next;  // Pointer to the next node
};

Second Step: Creating Two Nodes and Making Them Circular

Explanation:

• Create two nodes.

• Set the first node to point to the second node.

• Set the second node to point back to the first node (making it circular).

• Keep a pointer to the last node for easy access.

• Assign values to the nodes using scanf.

Code:

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

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

int main() {
    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));

    // Get values from the user
    printf("Enter value for the first node: ");
    scanf("%d", &first->data);
    first->next = second;

    printf("Enter value for the second node: ");
    scanf("%d", &second->data);
    second->next = first;  // Points back to first node (circular)

    // We can keep a pointer to the last node
    struct Node* last = second;

    // Free allocated memory
    free(first);
    free(second);

    return 0;
}

Third Step: Creating Three Nodes in a Circular List

Explanation:

• Create three nodes.

• Link them in a chain where each node points to the next node.

• The last node points back to the first node, completing the circle.

• This creates a circular structure: 1 -> 2 -> 3 -> 1 -> ...

Code:

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

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

int main() {
    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));

    // Get values from the user
    printf("Enter value for the first node: ");
    scanf("%d", &first->data);
    first->next = second;

    printf("Enter value for the second node: ");
    scanf("%d", &second->data);
    second->next = third;

    printf("Enter value for the third node: ");
    scanf("%d", &third->data);
    third->next = first;  // Points back to first node (circular)

    // Keep a pointer to the last node
    struct Node* last = third;

    // Free allocated memory
    free(first);
    free(second);
    free(third);

    return 0;
}

Fourth Step: Creating a Circular Linked List of 10 Nodes in a Loop

Explanation:

• Create a circular linked list with 10 nodes using a loop.

• Instead of a head pointer, we'll use a last pointer (tail).

• Each new node is inserted after the last node.

• The final step links the last node back to the first node.

• Use scanf to get values for each node from the user.

Code:

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

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

int main() {
    struct Node* last = NULL;    // Pointer to the last node
    struct Node* newNode = NULL; // Pointer to new node
    struct Node* first = NULL;   // To remember the first node

    // Create 10 nodes
    for (int i = 0; i < 10; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);

        if (last == NULL) {
            // First node in the list
            last = newNode;
            first = newNode;
            newNode->next = newNode; // Points to itself initially
        } else {
            // Insert after last node
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    // Make sure the last node points to the first node
    if (last != NULL) {
        last->next = first;
    }

    return 0;
}

Fifth Step: Printing the Circular Linked List

Explanation:

• Write a function that takes the last pointer as a parameter.

• Start from the first node (last->next).

• Use a do-while loop to traverse the list until we come back to the start.

• Be careful not to create an infinite loop!

• Print the data of each node.

Code:

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

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

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next; // Start from first node
    printf("Circular List: ");

    // Use do-while to ensure we print at least once
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

int main() {
    struct Node* last = NULL;
    struct Node* newNode = NULL;
    struct Node* first = NULL;

    // Create 5 nodes for demonstration
    for (int i = 0; i < 5; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);

        if (last == NULL) {
            last = newNode;
            first = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    // Print the circular list
    printCircularList(last);

    // Free allocated memory (be careful with circular references!)
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Sixth Step: Adding a Node at the Beginning

Explanation:

• Write a function that takes a double pointer to the last pointer.

• Create a new node, assign its value from the function parameter.

• If the list is empty, make the node point to itself.

• Otherwise, insert the new node after last (which makes it the first node).

• The last pointer remains unchanged.

Code:

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

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

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

// Function to add a node at the beginning
void addNodeAtBeginning(struct Node** pointerToLast, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;

    if (*pointerToLast == NULL) {
        // Empty list
        *pointerToLast = newNode;
        newNode->next = newNode;
    } else {
        // Insert after last (which puts it at the beginning)
        newNode->next = (*pointerToLast)->next;
        (*pointerToLast)->next = newNode;
    }
}

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

    // Create a simple circular list with 3 nodes
    for (int i = 1; i <= 3; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;

        if (last == NULL) {
            last = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    printf("Original list:\n");
    printCircularList(last);

    // Add a new node at the beginning
    int newValue;
    printf("Enter value for the new node at the beginning: ");
    scanf("%d", &newValue);
    addNodeAtBeginning(&last, newValue);

    printf("After adding at beginning:\n");
    printCircularList(last);

    // Free allocated memory
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Seventh Step: Adding a Node at the End

Explanation:

• Write a function that adds a node at the end of the circular list.

• Create a new node, assign its value from the function parameter.

• Insert the new node after the current last node.

• Update the last pointer to point to the new node.

• This operation is very efficient in circular lists!

Code:

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

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

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

// Function to add a node at the end
void addNodeAtEnd(struct Node** pointerToLast, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;

    if (*pointerToLast == NULL) {
        // Empty list
        *pointerToLast = newNode;
        newNode->next = newNode;
    } else {
        // Insert after last and update last pointer
        newNode->next = (*pointerToLast)->next;
        (*pointerToLast)->next = newNode;
        *pointerToLast = newNode;
    }
}

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

    // Create a simple circular list with 3 nodes
    for (int i = 1; i <= 3; i++) {
        addNodeAtEnd(&last, i);
    }

    printf("Original list:\n");
    printCircularList(last);

    // Add a new node at the end
    int newValue;
    printf("Enter value for the new node at the end: ");
    scanf("%d", &newValue);
    addNodeAtEnd(&last, newValue);

    printf("After adding at end:\n");
    printCircularList(last);

    // Free allocated memory
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Eighth Step: Deleting the First Node

Explanation:

• Write a function that takes a double pointer to the last pointer.

• Handle the special case of a single node (pointing to itself).

• Save the first node (last->next).

• Update last->next to skip the first node.

• Free the memory of the old first node.

Code:

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

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

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

// Function to delete the first node
void deleteFirstNode(struct Node** pointerToLast) {
    if (*pointerToLast == NULL) {
        return; // Empty list
    }

    struct Node* first = (*pointerToLast)->next;

    if (*pointerToLast == first) {
        // Only one node in the list
        free(first);
        *pointerToLast = NULL;
    } else {
        // More than one node
        (*pointerToLast)->next = first->next;
        free(first);
    }
}

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

    // Create a circular list with 4 nodes
    for (int i = 1; i <= 4; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;

        if (last == NULL) {
            last = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    printf("Original list:\n");
    printCircularList(last);

    // Delete the first node
    deleteFirstNode(&last);

    printf("After deleting first node:\n");
    printCircularList(last);

    // Free remaining memory
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Ninth Step: Deleting a Node with a Specific Value

Explanation:

• Write a function that takes a double pointer to the last pointer and a value.

• Traverse the list to find the node with the given value.

• Keep track of the previous node.

• Handle special cases: single node, deleting last node, deleting first node.

• Update the links to bypass the node and free its memory.

Code:

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

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

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

// Function to delete a node with a specific value
void deleteNodeWithValue(struct Node** pointerToLast, int value) {
    if (*pointerToLast == NULL) {
        return; // Empty list
    }

    struct Node* curr = (*pointerToLast)->next;
    struct Node* prev = *pointerToLast;

    // Single node case
    if (curr == *pointerToLast && curr->data == value) {
        free(curr);
        *pointerToLast = NULL;
        return;
    }

    // Search for the node
    do {
        if (curr->data == value) {
            // Found the node to delete
            prev->next = curr->next;

            // If we're deleting the last node, update last pointer
            if (curr == *pointerToLast) {
                *pointerToLast = prev;
            }

            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    } while (curr != (*pointerToLast)->next);

    printf("Value %d not found in the list\n", value);
}

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

    // Create a circular list with 5 nodes
    for (int i = 1; i <= 5; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i * 10;

        if (last == NULL) {
            last = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    printf("Original list:\n");
    printCircularList(last);

    // Delete a node with a specific value
    int valueToDelete;
    printf("Enter value to delete: ");
    scanf("%d", &valueToDelete);
    deleteNodeWithValue(&last, valueToDelete);

    printf("After deleting node with value %d:\n", valueToDelete);
    printCircularList(last);

    // Free remaining memory
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Tenth Step: Counting Nodes in a Circular List

Explanation:

• Write a function that counts the total number of nodes in the circular list.

• Start from the first node and traverse until we come back to the start.

• Use a counter to keep track of the number of nodes.

• Handle the empty list case.

Code:

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

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

// Function to count nodes in the circular list
int countNodes(struct Node* last) {
    if (last == NULL) {
        return 0;
    }

    int count = 0;
    struct Node* temp = last->next;

    do {
        count++;
        temp = temp->next;
    } while (temp != last->next);

    return count;
}

// Function to print the circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

int main() {
    struct Node* last = NULL;
    int n;

    printf("How many nodes do you want to create? ");
    scanf("%d", &n);

    // Create n nodes
    for (int i = 0; i < n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &newNode->data);

        if (last == NULL) {
            last = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = last->next;
            last->next = newNode;
            last = newNode;
        }
    }

    // Print the list
    printCircularList(last);

    // Count and display the number of nodes
    int nodeCount = countNodes(last);
    printf("Total number of nodes: %d\n", nodeCount);

    // Free allocated memory
    if (last != NULL) {
        struct Node* temp = last->next;
        while (temp != last) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
        free(last);
    }

    return 0;
}

Bonus Step: Converting Between Singly and Circular Linked Lists

Explanation:

• Write functions to convert a singly linked list to circular and vice versa.

• To convert singly to circular: find the last node and make it point to the first.

• To convert circular to singly: find the last node and make it point to NULL.

• These conversions show the relationship between the two structures.

Code:

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

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

// Function to print a singly linked list
void printSinglyList(struct Node* head) {
    printf("Singly List: ");
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Function to print a circular linked list
void printCircularList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = last->next;
    printf("Circular List: ");

    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != last->next);

    printf("(back to %d)\n", last->next->data);
}

// Convert singly linked list to circular
struct Node* convertToCircular(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }

    struct Node* last = head;

    // Find the last node
    while (last->next != NULL) {
        last = last->next;
    }

    // Make it circular
    last->next = head;

    return last; // Return the last pointer
}

// Convert circular linked list to singly
struct Node* convertToSingly(struct Node* last) {
    if (last == NULL) {
        return NULL;
    }

    struct Node* head = last->next;
    last->next = NULL; // Break the circle

    return head; // Return the head pointer
}

int main() {
    // Create a singly linked list with 4 nodes
    struct Node* head = NULL;
    struct Node* temp = NULL;

    for (int i = 1; i <= 4; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
        }
        temp = newNode;
    }

    printf("Original singly linked list:\n");
    printSinglyList(head);

    // Convert to circular
    struct Node* last = convertToCircular(head);
    printf("\nAfter converting to circular:\n");
    printCircularList(last);

    // Convert back to singly
    head = convertToSingly(last);
    printf("\nAfter converting back to singly:\n");
    printSinglyList(head);

    // Free memory
    temp = head;
    while (temp != NULL) {
        struct Node* next = temp->next;
        free(temp);
        temp = next;
    }

    return 0;
}