####################Circular Doubly Linked List############################
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *prev;
struct node *next;
} Node;
Node *last = NULL;
void create(int n);
void finsert(int data);
void linsert(int data);
void ainsert(int pos, int data);
void fdelete();
void ldelete();
void adelete(int pos);
void displayForward();
void displayBackward();
int count();
void search(int key);
void sort();
int main() {
int choice, n, data, pos, key;
while (1) {
printf("\n=== Circular Doubly Linked List Menu ===\n");
printf("1. Create\n2. Insert First\n3. Insert Last\n4. Insert at Position\n");
printf("5. Delete First\n6. Delete Last\n7. Delete at Position\n");
printf("8. Display Forward\n9. Display Backward\n10. Count\n");
printf("11. Search\n12. Sort\n13. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter number of nodes: ");
scanf("%d", &n);
create(n);
break;
case 2:
printf("Enter data: "); scanf("%d", &data);
finsert(data); break;
case 3:
printf("Enter data: "); scanf("%d", &data);
linsert(data); break;
case 4:
printf("Enter position: "); scanf("%d", &pos);
printf("Enter data: "); scanf("%d", &data);
ainsert(pos, data); break;
case 5: fdelete(); break;
case 6: ldelete(); break;
case 7:
printf("Enter position: "); scanf("%d", &pos);
adelete(pos); break;
case 8: displayForward(); break;
case 9: displayBackward(); break;
case 10: printf("Total nodes = %d\n", count()); break;
case 11:
printf("Enter key: "); scanf("%d", &key);
search(key); break;
case 12: sort(); break;
case 13: exit(0);
default: printf("Invalid choice!\n");
return 0;
void create(int n) {
int data, i;
for (i = 0; i < n; i++) {
printf("Enter data for node %d: ", i+1);
scanf("%d", &data);
linsert(data);
void finsert(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if (last == NULL) {
last = newNode;
last->next = last;
last->prev = last;
} else {
newNode->next = last->next;
newNode->prev = last;
last->next->prev = newNode;
last->next = newNode;
void linsert(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if (last == NULL) {
last = newNode;
last->next = last;
last->prev = last;
} else {
newNode->next = last->next;
newNode->prev = last;
last->next->prev = newNode;
last->next = newNode;
last = newNode;
void ainsert(int pos, int data) {
if (pos == 1) { finsert(data); return; }
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
Node *temp = last->next;
int i;
for (i = 1; i < pos-1 && temp != last; i++) {
temp = temp->next;
newNode->next = temp->next;
newNode->prev = temp;
temp->next->prev = newNode;
temp->next = newNode;
if (temp == last) last = newNode;
void fdelete() {
if (last == NULL) { printf("Empty!\n"); return; }
Node *temp = last->next;
if (last == last->next) {
free(last); last = NULL;
} else {
last->next = temp->next;
temp->next->prev = last;
free(temp);
void ldelete() {
if (last == NULL) { printf("Empty!\n"); return; }
if (last == last->next) {
free(last); last = NULL;
} else {
Node *temp = last;
last->prev->next = last->next;
last->next->prev = last->prev;
last = last->prev;
free(temp);
void adelete(int pos) {
if (last == NULL) { printf("Empty!\n"); return; }
if (pos == 1) { fdelete(); return; }
Node *temp = last->next; int i;
for (i = 1; i < pos && temp != last; i++) {
temp = temp->next;
if (i != pos) { printf("Invalid position!\n"); return; }
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
if (temp == last) last = last->prev;
free(temp);
void displayForward() {
if (last == NULL) { printf("Empty!\n"); return; }
Node *temp = last->next;
printf("List (Forward): ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != last->next);
printf("\n");
void displayBackward() {
if (last == NULL) { printf("Empty!\n"); return; }
Node *temp = last;
printf("List (Backward): ");
do {
printf("%d ", temp->data);
temp = temp->prev;
} while (temp != last);
printf("%d\n", temp->data);
int count() {
if (last == NULL) return 0;
int c = 0; Node *temp = last->next;
do { c++; temp = temp->next; } while (temp != last->next);
return c;
void search(int key) {
if (last == NULL) { printf("Empty!\n"); return; }
Node *temp = last->next; int pos = 1;
do {
if (temp->data == key) {
printf("Found %d at position %d\n", key, pos);
return;
}
pos++; temp = temp->next;
} while (temp != last->next);
printf("Not found!\n");
void sort() {
if (last == NULL || last->next == last) return;
Node *i, *j; int t;
for (i = last->next; i->next != last->next; i = i->next) {
for (j = i->next; j != last->next; j = j->next) {
if (i->data > j->data) {
t = i->data; i->data = j->data; j->data = t;
Algorithm for Circular Doubly Linked List (CDLL)
1. Create List
1. Start
2. Input number of nodes n
3. Repeat for each node:
o Allocate new node
o Input data
o If list empty → last = newNode, newNode->next = newNode, newNode->prev
= newNode
o Else → Insert at last
4. Stop
2. Insertion at Beginning
Algorithm:
1. Start.
2. Create a new node with given data.
3. If list is empty:
o Set head = newnode, newnode->next = newnode, newnode->prev =
newnode.
4. Else:
o Link newnode before head.
o Update last node’s next to point to newnode.
o Update head->prev to newnode.
o Make head = newnode.
5. Stop.
3. Insertion at End
Algorithm:
1. Start.
2. Create a new node with given data.
3. If list is empty:
o Set head = newnode, newnode->next = newnode, newnode->prev =
newnode.
4. Else:
o Insert newnode before head.
o Update last node’s next and head->prev accordingly.
5. Stop.
4. Insertion at Any Position
Algorithm:
1. Start.
2. Input position and data.
3. Traverse the list to reach (position - 1)th node.
4. Create a new node.
5. Adjust links:
o newnode->next = current->next.
o newnode->prev = current.
o current->next->prev = newnode.
o current->next = newnode.
6. Stop.
5. Deletion at Beginning
Algorithm:
1. Start.
2. If list is empty → Print “Underflow” and Stop.
3. If only one node:
o Free node and set head = NULL.
4. Else:
o Update last node’s next = head->next.
o Update head->next->prev = last.
o Free old head.
o Set head = head->next.
5. Stop.
6. Deletion at End
Algorithm:
1. Start.
2. If list is empty → Print “Underflow” and Stop.
3. If only one node:
o Free node and set head = NULL.
4. Else:
o Traverse to last node.
o Update second last node’s next = head.
o Update head->prev = second last.
o Free last node.
5. Stop.
7. Deletion at Any Position
Algorithm:
1. Start.
2. If list is empty → Print “Underflow” and Stop.
3. Input position.
4. Traverse to (position)th node.
5. Update links:
o node->prev->next = node->next.
o node->next->prev = node->prev.
6. Free the node.
7. If deleted node was head, update head = head->next.
8. Stop.
8. Traversal (Display Forward)
Algorithm:
1. Start.
2. If list is empty → Print “Empty”.
3. Else:
o Initialize temp = head.
o Repeat:
Print temp->data.
Move temp = temp->next.
o Until temp == head.
4. Stop.
9. Traversal (Display Backward)
Algorithm:
1. Start.
2. If list is empty → Print “Empty”.
3. Else:
o Initialize temp = head->prev (last node).
o Repeat:
Print temp->data.
Move temp = temp->prev.
o Until temp == head->prev.
4. Stop.
10. Count Nodes
Algorithm:
1. Start.
2. If list is empty → Count = 0.
3. Else:
o Initialize count = 0 and temp = head.
o Repeat:
Increment count.
Move temp = temp->next.
o Until temp == head.
4. Print count.
5. Stop.
11. Search Element
Algorithm:
1. Start.
2. Input key.
3. Initialize temp = head, pos = 1.
4. Repeat:
o If temp->data == key → Print found at pos and Stop.
o Else → Move temp = temp->next, Increment pos.
o Until temp == head.
5. If not found → Print “Not Found”.
6. Stop.
12. Sort Nodes
Algorithm:
1. Start.
2. If list is empty or only one node → Stop.
3. Else:
o Use Bubble Sort technique:
o Repeat until no swaps:
Traverse from head to head->prev (last).
Compare adjacent nodes’ data.
Swap if out of order.
4. Stop.
Difference between Singly and Circular linked list:
