Algorithm and Program in C to traverse Doubly Circular Linked List

A doubly circular linked list (DCLL) is an advanced variation of a linked list where each node contains a data field and two pointers: one pointing to the next node and one pointing to the previous node. Unlike a standard doubly linked list, the DCLL is circular, meaning the next pointer of the last node points to the head node, and the prev pointer of the head node points to the last node. This bidirectional and circular linkage allows traversal in both directions from any node and enables continuous looping through the list without encountering a NULL pointer.

Such a structure is particularly useful in applications requiring round-robin access, cyclic buffers, and repeated iteration over a dataset, as it provides efficient insertion, deletion, and traversal at any point in the list while maintaining constant connectivity.

What is a Doubly Circular Linked List?

A Doubly Circular Linked List has the following properties:

• Each node has three parts: data, a pointer to the next node, and a pointer to the previous node.
• The last node’s next pointer links back to the head node.
• The head node’s prev pointer links to the last node.
• You can traverse it forwards or backwards in a circular manner.

Algorithm to Traverse a Doubly Circular Linked List

Here’s a clear and simple algorithm to traverse the list in the forward direction:

Algorithm

Step 1: Start from the head node
Step 2: Repeat the following steps until you reach back to the head node:

• Print the data of the current node
• Move to the next node

Step 3: Stop

Note: Before starting the traversal, always check if the list is empty (i.e., head is NULL).

C Program to Create and Traverse

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

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

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = newNode->prev = NULL;
    return newNode;
}

// Function to insert node at the end of the list
void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {
        newNode->next = newNode->prev = newNode;
        *head = newNode;
    } else {
        struct Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = newNode;
        (*head)->prev = newNode;
    }
}

// Function to traverse the doubly circular linked list
void traverseList(struct Node* head) {
    if (head == NULL) {
        printf("The list is empty.\n");
        return;
    }

    struct Node* temp = head;
    printf("Doubly Circular Linked List (Forward): ");
    do {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to head)\n");
}

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

    // Inserting nodes
    insertAtEnd(&head, 5);
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 15);
    insertAtEnd(&head, 20);

    // Traversing the list
    traverseList(head);

    return 0;
}

Output

Doubly Circular Linked List (Forward): 5 <-> 10 <-> 15 <-> 20 <-> (back to head)

Explanation of Code

The above code demonstrates how to create, insert, and traverse a doubly circular linked list (DCLL) in C. A DCLL is a linked list where each node contains data and two pointers, next and prev, allowing traversal in both directions, and the last node points back to the head, forming a circular structure. The program defines a Node structure and a createNode() function that allocates memory for a new node and initializes its data and pointers. The insertAtEnd() function adds a new node at the end of the list: if the list is empty, the new node points to itself and becomes the head; if not, the new node is linked between the last node and the head, maintaining both the doubly-linked and circular properties. The traverseList() function prints all the elements starting from the head, moving forward until it returns to the head, showing the circular nature of the list. In the main() function, nodes with values 5, 10, 15, and 20 are inserted, and the list is traversed to display them. This program highlights the bidirectional traversal, circular linking, and dynamic insertion features of a doubly circular linked list.

Time & Space Complexity

Time Complexity

Space Complexity