Algorithm and Program in C to traverse Doubly Circular Linked List

A doubly circular linked list is a special type of linked list in which every node is connected to both the previous and the next node, and the list forms a circle — the last node links back to the first, and the first links back to the last. This structure allows bidirectional traversal and seamless looping through the list.

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)