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

Command Palette

Comments

More from this blog

First Step: What is a Circular Linked List?

Explanation:

Code:

Second Step: Creating Two Nodes and Making Them Circular

Explanation:

Code:

Third Step: Creating Three Nodes in a Circular List

Explanation:

Code:

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

Explanation:

Code:

Fifth Step: Printing the Circular Linked List

Explanation:

Code:

Sixth Step: Adding a Node at the Beginning

Explanation:

Code:

Seventh Step: Adding a Node at the End

Explanation:

Code:

Eighth Step: Deleting the First Node

Explanation:

Code:

Ninth Step: Deleting a Node with a Specific Value

Explanation:

Code:

Tenth Step: Counting Nodes in a Circular List

Explanation:

Code:

Bonus Step: Converting Between Singly and Circular Linked Lists

Explanation:

Code: