Circular Doubly Linked List

A Circular Doubly Linked List (CDLL) is a variation of a doubly linked list where:

• Each node contains three parts:
  data, prev pointer, and next pointer.
• The last node's next pointer points to the first node (head).
• The first node's prev pointer points to the last node, forming a circular connection in both directions.

Characteristics

• Each node points both to next and previous nodes.
• Circular: The list has no NULL at the ends — it loops back.
• Can be traversed in both directions (forward and backward).
• Suitable for navigation-based tasks, like playlists, image viewers, etc.

The last hub of the rundown contains the location of the main hub of the rundown. The main hub of the rundown additionally contain address of the last hub in its past pointer. A circular doubly linked list is shown in the following figure.

Because of the way that a round doubly connected rundown contains three sections in its design hence, it requests more space per hub and more costly essential activities. Be that as it may, a round doubly connected rundown gives simple control of the pointers and the looking turns out to be twice as proficient

Memory Management of Circular Doubly linked list

The accompanying figure shows the manner by which the memory is designated for a round doubly connected rundown. The variable head contains the location of the principal component of the rundown for example 1 consequently the beginning hub of the rundown contains information An is put away at address 1.

Since, every hub of the rundown should have three sections along these lines, the beginning hub of the rundown contains address of the last hub for example 8 and the following hub for example 4.

The last hub of the rundown that is put away at address 8 and containing information as 6, contains address of the primary hub of the rundown as demonstrated in the picture for example 1. In roundabout doubly connected rundown, the last hub is recognized by the location of the main hub which is put away in the following piece of the last hub hence the hub which contains the location of the principal hub, is really the last hub of the rundown.

Operations on circular doubly linked list :

There are different tasks which can be performed on round doubly connected rundown. The hub design of a roundabout doubly connected rundown is like doubly connected rundown. Be that as it may, the procedure on round doubly connected rundown is portrayed in the accompanying table.

Traversing and searching in circular doubly linked list is similar to that in the circular singly linked list.

Advantages

• Bi-directional traversal: You can go both forward and backward.
• Circular nature: No need to handle end conditions specially; you can keep cycling through.
• Efficient insertions/deletions: Especially when the pointer to the node is given.
• Good for real-time systems where looping through data is needed.

C program to implement all the operations on circular doubly linked list

Here's a complete C program implementing all major operations on a Circular Doubly Linked List

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

// Node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

struct Node* head = NULL;

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

// Insert at beginning
void insertAtBeginning(int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        newNode->next = newNode->prev = newNode;
        head = newNode;
    } else {
        struct Node* tail = head->prev;

        newNode->next = head;
        newNode->prev = tail;
        tail->next = newNode;
        head->prev = newNode;

        head = newNode;
    }
    printf("%d inserted at beginning\n", value);
}

// Insert at end
void insertAtEnd(int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        newNode->next = newNode->prev = newNode;
        head = newNode;
    } else {
        struct Node* tail = head->prev;

        tail->next = newNode;
        newNode->prev = tail;
        newNode->next = head;
        head->prev = newNode;
    }
    printf("%d inserted at end\n", value);
}

// Insert at position
void insertAtPosition(int value, int pos) {
    if (pos <= 0) {
        printf("Invalid position\n");
        return;
    }

    if (pos == 1) {
        insertAtBeginning(value);
        return;
    }

    struct Node* temp = head;
    struct Node* newNode = createNode(value);

    for (int i = 1; i < pos - 1 && temp->next != head; i++) {
        temp = temp->next;
    }

    if (temp->next == head) {
        insertAtEnd(value);
        return;
    }

    newNode->next = temp->next;
    newNode->prev = temp;
    temp->next->prev = newNode;
    temp->next = newNode;

    printf("%d inserted at position %d\n", value, pos);
}

// Delete from beginning
void deleteFromBeginning() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    if (head->next == head) {
        free(head);
        head = NULL;
    } else {
        struct Node* tail = head->prev;
        struct Node* temp = head;

        head = head->next;
        head->prev = tail;
        tail->next = head;

        free(temp);
    }
    printf("Deleted from beginning\n");
}

// Delete from end
void deleteFromEnd() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    if (head->next == head) {
        free(head);
        head = NULL;
    } else {
        struct Node* tail = head->prev;
        struct Node* newTail = tail->prev;

        newTail->next = head;
        head->prev = newTail;

        free(tail);
    }
    printf("Deleted from end\n");
}

// Delete from position
void deleteFromPosition(int pos) {
    if (head == NULL || pos <= 0) {
        printf("Invalid operation\n");
        return;
    }

    if (pos == 1) {
        deleteFromBeginning();
        return;
    }

    struct Node* temp = head;
    for (int i = 1; i < pos && temp->next != head; i++) {
        temp = temp->next;
    }

    if (temp == head) {
        printf("Position out of range\n");
        return;
    }

    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    free(temp);

    printf("Deleted node from position %d\n", pos);
}

// Forward traversal
void displayForward() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = head;
    printf("Forward: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

// Reverse traversal
void displayReverse() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* tail = head->prev;
    struct Node* temp = tail;
    printf("Reverse: ");
    do {
        printf("%d ", temp->data);
        temp = temp->prev;
    } while (temp != tail);
    printf("\n");
}

// Search operation
void search(int key) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = head;
    int pos = 1;
    do {
        if (temp->data == key) {
            printf("Found %d at position %d\n", key, pos);
            return;
        }
        temp = temp->next;
        pos++;
    } while (temp != head);

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

// Main function
int main() {
    insertAtEnd(10);
    insertAtEnd(20);
    insertAtEnd(30);
    displayForward();

    insertAtBeginning(5);
    displayForward();

    insertAtPosition(25, 3);
    displayForward();
    displayReverse();

    deleteFromBeginning();
    displayForward();

    deleteFromEnd();
    displayForward();

    deleteFromPosition(2);
    displayForward();

    search(20);
    search(100);

    return 0;
}

Output

10 inserted at end
20 inserted at end
30 inserted at end
Forward: 10 20 30
5 inserted at beginning
Forward: 5 10 20 30
25 inserted at position 3
Forward: 5 10 25 20 30
Reverse: 30 20 25 10 5
Deleted from beginning
Forward: 10 25 20 30
Deleted from end
Forward: 10 25 20
Deleted node from position 2
Forward: 10 20
Found 20 at position 2
100 not found in the list