Data Structures and Algorithms_Linked List.4

Circular Linked List

Simple explanation and C code for creating circular linked list

One issue faced with singly one way linked list ( or simply linked list) is that its like a one way road -> once you go forward , you can’t traverse back. ( much like life don’t you think?)

This issue is solved by a Circular Linked List. Here the last node’s link rather than set to NULL, is linked to the head node, making it possible to traverse back. (Time travel made possible 🤣)

Image representing circular linked list.

Now, (drum roll please)

The C code!

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

struct node {
    int info;
    struct node *link;
};

int main() {
    int i;
    struct node *ptr, *q, *head;
    
    // Create the head node
    head = (struct node *) malloc(sizeof(struct node));
    head->info = 1; // Start with the first meaningful value
    head->link = NULL;
    
    ptr = head; // Set ptr to head

    // Create other nodes
    for (i = 2; i < 10; i++) { 
        q = (struct node *) malloc(sizeof(struct node));
        q->info = i;
        q->link = NULL;
        
        ptr->link = q; // Link the nodes
        ptr = q; // Move ptr to the new node
    }

    // Make it circular
    ptr->link = head; // Point the last node to head

    // Printing values
    ptr = head; // Start from head
    do {
        printf("%d -> ", ptr->info);
        ptr = ptr->link;
    } while (ptr != head);
    
    printf("(back to %d)\n", head->info); // Indicate circularity
    return 0;
}