1. Introduction

A Circular Doubly Linked List (CDLL) is a combination of:

Doubly linked list (two pointers: prev, next)
Circular linked list (last node connects back to first, and vice-versa)

A Circular Doubly Linked List is a linked list where:

Each node has:
- data
- prev pointer
- next pointer
The last node’s next points to the first node
The first node’s prev points to the last node

Thus the list becomes a closed loop in both directions.

       prev ←----→ next
   ┌───────────────────────┐
   ↓                       ↓
[Node1] ⇆ [Node2] ⇆ [Node3]
   ↑                       ↑
   └──────────────→────────┘

2. Node Structure in C

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

Explanation

data – holds integer element
prev – points to previous node
next – points to next node

In a CDLL:

head->prev points to last node
last->next points to head

3. Creating a Node

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

4. Insertion Operations

4.1 Insert at Beginning

Logic

If list empty → newNode->next = newNode->prev = newNode
Else:
- newNode becomes new head
- Update old head and last node links

C Code

void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = createNode(value);

    if (*head == NULL) {
        newNode->next = newNode->prev = newNode;
        *head = newNode;
        return;
    }

    struct Node* last = (*head)->prev;

    newNode->next = *head;
    newNode->prev = last;

    last->next = newNode;
    (*head)->prev = newNode;

    *head = newNode;
}

4.2 Insert at End

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);

    if (*head == NULL) {
        newNode->next = newNode->prev = newNode;
        *head = newNode;
        return;
    }

    struct Node* last = (*head)->prev;

    last->next = newNode;
    newNode->prev = last;
    newNode->next = *head;
    (*head)->prev = newNode;
}

4.3 Insert After Given Position

void insertAtPosition(struct Node** head, int value, int pos) {
    if (*head == NULL) {
        printf("List empty, inserting at beginning\n");
        insertAtBeginning(head, value);
        return;
    }

    struct Node* temp = *head;
    int i = 1;

    while (i < pos && temp->next != *head) {
        temp = temp->next;
        i++;
    }

    struct Node* newNode = createNode(value);

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

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

5. Deletion Operations

5.1 Delete from Beginning

void deleteAtBeginning(struct Node** head) {
    if (*head == NULL) {
        printf("List empty\n");
        return;
    }

    struct Node* temp = *head;

    // only one node
    if (temp->next == temp) {
        free(temp);
        *head = NULL;
        return;
    }

    struct Node* last = temp->prev;

    *head = temp->next;
    last->next = *head;
    (*head)->prev = last;

    free(temp);
}

5.2 Delete Last Node

void deleteAtEnd(struct Node** head) {
    if (*head == NULL) {
        printf("List empty\n");
        return;
    }

    struct Node* last = (*head)->prev;

    // Only one node
    if (last == *head) {
        free(last);
        *head = NULL;
        return;
    }

    struct Node* secondLast = last->prev;

    secondLast->next = *head;
    (*head)->prev = secondLast;

    free(last);
}

5.3 Delete from Position

void deleteAtPosition(struct Node** head, int pos) {
    if (*head == NULL) {
        printf("List empty\n");
        return;
    }

    struct Node* temp = *head;

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

    if (temp->next == temp) {   // Only one node
        free(temp);
        *head = NULL;
        return;
    }

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

    if (temp == *head)
        *head = temp->next;

    free(temp);
}

6. Display Operations

6.1 Forward Traversal

void displayForward(struct Node* head) {
    if (head == NULL) {
        printf("List empty\n");
        return;
    }

    struct Node* temp = head;

    do {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    } while (temp != head);

    printf("(Back to Head)\n");
}

6.2 Reverse Traversal

void displayBackward(struct Node* head) {
    if (head == NULL) {
        printf("List empty\n");
        return;
    }

    struct Node* last = head->prev;

    struct Node* temp = last;

    do {
        printf("%d <-> ", temp->data);
        temp = temp->prev;
    } while (temp != last);

    printf("(Back to Tail)\n");
}

7. Time & Space Complexity

Operation	CDLL Complexity
Insert at beginning	O(1)
Insert at end	O(1)
Delete first	O(1)
Delete last	O(1)
Insert at position	O(n)
Delete at position	O(n)
Searching	O(n)
Total space	O(n)

8. Memory Diagram

   head
    ↓
 [10] ⇆ [20]   ⇆ [30]
  ↑                 ↓
  └──────⇦⇦⇦──────┘

 head->prev = 30
 last->next = head

9. Complete Working Program

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

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

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

void insertAtBeginning(struct Node** head, int value);
void insertAtEnd(struct Node** head, int value);
void insertAtPosition(struct Node** head, int value, int pos);
void deleteAtBeginning(struct Node** head);
void deleteAtEnd(struct Node** head);
void deleteAtPosition(struct Node** head, int pos);
void displayForward(struct Node* head);
void displayBackward(struct Node* head);

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

    insertAtBeginning(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtPosition(&head, 15, 1);

    printf("Forward: ");
    displayForward(head);

    printf("Backward: ");
    displayBackward(head);

    deleteAtPosition(&head, 2);
    displayForward(head);

    return 0;
}