Introduction to Circular Linked List

A circular linked list is a variation of a linked list where the last node points back to the first node, forming a circle. This structure is useful for applications that require cyclic traversal, such as round-robin scheduling, circular buffers, and multiplayer game loops.

---

Circular Linked List Architecture

Circular Linked List Structure
├── Node Structure
│   ├── Data (any type)
│   └── Next (pointer to next node)
├── List Structure
│   ├── Head (first node)
│   ├── Tail (last node)
│   └── Size (number of nodes)
└── Traversal
├── Forward only (singly circular)
├── Both directions (doubly circular)
└── Wraps around at end

Singly Circular Linked List

     ┌─────┐     ┌─────┐     ┌─────┐
│  1  │     │  2  │     │  3  │
│ next─────→│ next─────→│ next───┐
└─────┘     └─────┘     └─────┘   │
↑                               │
└───────────────────────────────┘

Doubly Circular Linked List

     ┌───────────┐     ┌───────────┐     ┌───────────┐
│ prev ←────│─────│ prev ←────│─────│ prev ←────│─────┐
│    1      │     │    2      │     │    3      │     │
│ next ────→│─────│ next ────→│─────│ next ────→│─────┘
└───────────┘     └───────────┘     └───────────┘
↑                                                   │
└───────────────────────────────────────────────────┘

---

Core Implementation

1. Node and List Structure

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Node structure for singly circular linked list
typedef struct Node {
int data;
struct Node* next;
} Node;
// Node structure for doubly circular linked list
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
// List structure for singly circular linked list
typedef struct {
Node* head;
Node* tail;
int size;
} CircularList;
// List structure for doubly circular linked list
typedef struct {
DNode* head;
DNode* tail;
int size;
} DoublyCircularList;

2. Basic Operations - Singly Circular Linked List

// Initialize circular linked list
void initList(CircularList* list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
// Create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Check if list is empty
bool isEmpty(CircularList* list) {
return list->size == 0;
}
// Get size of list
int getSize(CircularList* list) {
return list->size;
}

3. Insertion Operations

Insert at Beginning

void insertAtBeginning(CircularList* list, int data) {
Node* newNode = createNode(data);
if (isEmpty(list)) {
// First node
list->head = newNode;
list->tail = newNode;
newNode->next = newNode;  // Point to itself
} else {
newNode->next = list->head;
list->head = newNode;
list->tail->next = list->head;  // Maintain circular connection
}
list->size++;
printf("Inserted %d at beginning\n", data);
}

Insert at End

void insertAtEnd(CircularList* list, int data) {
Node* newNode = createNode(data);
if (isEmpty(list)) {
list->head = newNode;
list->tail = newNode;
newNode->next = newNode;
} else {
newNode->next = list->head;
list->tail->next = newNode;
list->tail = newNode;
}
list->size++;
printf("Inserted %d at end\n", data);
}

Insert at Position

void insertAtPosition(CircularList* list, int data, int position) {
if (position < 0 || position > list->size) {
printf("Invalid position!\n");
return;
}
if (position == 0) {
insertAtBeginning(list, data);
return;
}
if (position == list->size) {
insertAtEnd(list, data);
return;
}
Node* newNode = createNode(data);
Node* current = list->head;
// Traverse to position - 1
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
list->size++;
printf("Inserted %d at position %d\n", data, position);
}

Insert After Value

void insertAfterValue(CircularList* list, int searchData, int newData) {
if (isEmpty(list)) {
printf("List is empty!\n");
return;
}
Node* current = list->head;
do {
if (current->data == searchData) {
Node* newNode = createNode(newData);
newNode->next = current->next;
current->next = newNode;
// Update tail if inserted after tail
if (current == list->tail) {
list->tail = newNode;
}
list->size++;
printf("Inserted %d after %d\n", newData, searchData);
return;
}
current = current->next;
} while (current != list->head);
printf("Value %d not found in the list\n", searchData);
}

4. Deletion Operations

Delete from Beginning

int deleteFromBeginning(CircularList* list) {
if (isEmpty(list)) {
printf("List is empty!\n");
return -1;
}
int deletedData;
if (list->size == 1) {
// Only one node
deletedData = list->head->data;
free(list->head);
list->head = NULL;
list->tail = NULL;
} else {
Node* temp = list->head;
deletedData = temp->data;
list->head = list->head->next;
list->tail->next = list->head;
free(temp);
}
list->size--;
printf("Deleted %d from beginning\n", deletedData);
return deletedData;
}

Delete from End

int deleteFromEnd(CircularList* list) {
if (isEmpty(list)) {
printf("List is empty!\n");
return -1;
}
int deletedData;
if (list->size == 1) {
deletedData = list->head->data;
free(list->head);
list->head = NULL;
list->tail = NULL;
} else {
Node* current = list->head;
// Traverse to node before tail
while (current->next != list->tail) {
current = current->next;
}
deletedData = list->tail->data;
free(list->tail);
current->next = list->head;
list->tail = current;
}
list->size--;
printf("Deleted %d from end\n", deletedData);
return deletedData;
}

Delete by Value

int deleteByValue(CircularList* list, int value) {
if (isEmpty(list)) {
printf("List is empty!\n");
return -1;
}
// Check if head node contains the value
if (list->head->data == value) {
return deleteFromBeginning(list);
}
Node* current = list->head;
Node* prev = NULL;
do {
prev = current;
current = current->next;
if (current->data == value) {
prev->next = current->next;
// Update tail if last node is deleted
if (current == list->tail) {
list->tail = prev;
}
int deletedData = current->data;
free(current);
list->size--;
printf("Deleted %d\n", deletedData);
return deletedData;
}
} while (current != list->head);
printf("Value %d not found in the list\n", value);
return -1;
}

Delete from Position

int deleteFromPosition(CircularList* list, int position) {
if (isEmpty(list)) {
printf("List is empty!\n");
return -1;
}
if (position < 0 || position >= list->size) {
printf("Invalid position!\n");
return -1;
}
if (position == 0) {
return deleteFromBeginning(list);
}
if (position == list->size - 1) {
return deleteFromEnd(list);
}
Node* current = list->head;
Node* prev = NULL;
for (int i = 0; i < position; i++) {
prev = current;
current = current->next;
}
prev->next = current->next;
int deletedData = current->data;
free(current);
list->size--;
printf("Deleted %d from position %d\n", deletedData, position);
return deletedData;
}

5. Traversal and Search Operations

Display List

void displayList(CircularList* list) {
if (isEmpty(list)) {
printf("List is empty\n");
return;
}
printf("Circular Linked List (size = %d): ", list->size);
Node* current = list->head;
do {
printf("%d -> ", current->data);
current = current->next;
} while (current != list->head);
printf("(back to head: %d)\n", list->head->data);
}
// Display with position numbers
void displayWithPositions(CircularList* list) {
if (isEmpty(list)) {
printf("List is empty\n");
return;
}
printf("Circular Linked List:\n");
Node* current = list->head;
int pos = 0;
do {
printf("[%d]: %d\n", pos++, current->data);
current = current->next;
} while (current != list->head);
printf("Total nodes: %d\n", list->size);
}

Search for Value

int searchValue(CircularList* list, int value) {
if (isEmpty(list)) {
return -1;
}
Node* current = list->head;
int position = 0;
do {
if (current->data == value) {
printf("Value %d found at position %d\n", value, position);
return position;
}
current = current->next;
position++;
} while (current != list->head);
printf("Value %d not found in the list\n", value);
return -1;
}

Get Node at Position

Node* getNodeAtPosition(CircularList* list, int position) {
if (isEmpty(list) || position < 0 || position >= list->size) {
return NULL;
}
Node* current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
return current;
}

6. Advanced Operations

Reverse Circular Linked List

void reverseList(CircularList* list) {
if (isEmpty(list) || list->size == 1) {
return;
}
Node* prev = list->tail;
Node* current = list->head;
Node* next = NULL;
do {
next = current->next;
current->next = prev;
prev = current;
current = next;
} while (current != list->head);
// Update head and tail
list->tail = list->head;
list->head = prev;
printf("List reversed successfully\n");
}

Split List into Two Halves

void splitList(CircularList* source, CircularList* list1, CircularList* list2) {
if (isEmpty(source) || source->size < 2) {
return;
}
int mid = source->size / 2;
// Initialize destination lists
initList(list1);
initList(list2);
Node* current = source->head;
// First half
for (int i = 0; i < mid; i++) {
insertAtEnd(list1, current->data);
current = current->next;
}
// Second half
do {
insertAtEnd(list2, current->data);
current = current->next;
} while (current != source->head);
printf("List split into two halves\n");
}

Merge Two Sorted Circular Lists

void mergeSortedLists(CircularList* list1, CircularList* list2, CircularList* result) {
initList(result);
Node* p = list1->head;
Node* q = list2->head;
if (isEmpty(list1) && isEmpty(list2)) {
return;
}
if (isEmpty(list1)) {
// Copy list2 to result
do {
insertAtEnd(result, q->data);
q = q->next;
} while (q != list2->head);
return;
}
if (isEmpty(list2)) {
// Copy list1 to result
do {
insertAtEnd(result, p->data);
p = p->next;
} while (p != list1->head);
return;
}
// Merge both lists
int pProcessed = 0, qProcessed = 0;
int totalSize = list1->size + list2->size;
for (int i = 0; i < totalSize; i++) {
if (pProcessed < list1->size && qProcessed < list2->size) {
if (p->data <= q->data) {
insertAtEnd(result, p->data);
p = p->next;
pProcessed++;
} else {
insertAtEnd(result, q->data);
q = q->next;
qProcessed++;
}
} else if (pProcessed < list1->size) {
insertAtEnd(result, p->data);
p = p->next;
pProcessed++;
} else {
insertAtEnd(result, q->data);
q = q->next;
qProcessed++;
}
}
printf("Merged sorted lists successfully\n");
}

Remove Duplicates

void removeDuplicates(CircularList* list) {
if (isEmpty(list) || list->size == 1) {
return;
}
Node* current = list->head;
do {
Node* runner = current;
while (runner->next != list->head) {
if (runner->next->data == current->data) {
// Duplicate found
Node* temp = runner->next;
runner->next = temp->next;
if (temp == list->tail) {
list->tail = runner;
}
free(temp);
list->size--;
} else {
runner = runner->next;
}
}
current = current->next;
} while (current != list->head);
printf("Duplicates removed\n");
}

Rotate List

void rotateList(CircularList* list, int k) {
if (isEmpty(list) || k % list->size == 0) {
return;
}
k = k % list->size;  // Normalize rotation
if (k < 0) {
k = list->size + k;  // Handle negative rotation
}
// Find new head position
Node* current = list->head;
for (int i = 0; i < k - 1; i++) {
current = current->next;
}
// Update pointers
list->tail = current;
list->head = current->next;
printf("List rotated by %d positions\n", k);
}

7. Josephus Problem (Classic Circular List Application)

int josephusProblem(int n, int k) {
CircularList list;
initList(&list);
// Create circular list with n people
for (int i = 1; i <= n; i++) {
insertAtEnd(&list, i);
}
printf("Josephus Problem: %d people, eliminate every %dth person\n", n, k);
displayList(&list);
Node* current = list.head;
Node* prev = list.tail;
while (list.size > 1) {
// Skip k-1 people
for (int count = 1; count < k; count++) {
prev = current;
current = current->next;
}
// Eliminate current person
printf("Eliminated: %d\n", current->data);
prev->next = current->next;
free(current);
list.size--;
current = prev->next;
if (list.size == 1) {
list.head = current;
list.tail = current;
current->next = current;
}
}
int survivor = list.head->data;
printf("Survivor: %d\n", survivor);
free(list.head);
return survivor;
}

8. Memory Management

Free Entire List

void freeList(CircularList* list) {
if (isEmpty(list)) {
return;
}
Node* current = list->head;
Node* next;
do {
next = current->next;
free(current);
current = next;
} while (current != list->head);
list->head = NULL;
list->tail = NULL;
list->size = 0;
printf("List memory freed\n");
}

---

Doubly Circular Linked List Implementation

1. Basic Operations for Doubly Circular

// Initialize doubly circular linked list
void initDoublyList(DoublyCircularList* list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
// Create a new node for doubly circular list
DNode* createDNode(int data) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Insert at beginning (doubly circular)
void insertAtBeginningDoubly(DoublyCircularList* list, int data) {
DNode* newNode = createDNode(data);
if (list->size == 0) {
list->head = newNode;
list->tail = newNode;
newNode->prev = newNode;
newNode->next = newNode;
} else {
newNode->next = list->head;
newNode->prev = list->tail;
list->head->prev = newNode;
list->tail->next = newNode;
list->head = newNode;
}
list->size++;
printf("Inserted %d at beginning\n", data);
}
// Insert at end (doubly circular)
void insertAtEndDoubly(DoublyCircularList* list, int data) {
DNode* newNode = createDNode(data);
if (list->size == 0) {
list->head = newNode;
list->tail = newNode;
newNode->prev = newNode;
newNode->next = newNode;
} else {
newNode->prev = list->tail;
newNode->next = list->head;
list->tail->next = newNode;
list->head->prev = newNode;
list->tail = newNode;
}
list->size++;
printf("Inserted %d at end\n", data);
}
// Display forward (doubly circular)
void displayForward(DoublyCircularList* list) {
if (list->size == 0) {
printf("List is empty\n");
return;
}
printf("Forward traversal: ");
DNode* current = list->head;
do {
printf("%d <-> ", current->data);
current = current->next;
} while (current != list->head);
printf("(back to head)\n");
}
// Display backward (doubly circular)
void displayBackward(DoublyCircularList* list) {
if (list->size == 0) {
printf("List is empty\n");
return;
}
printf("Backward traversal: ");
DNode* current = list->tail;
do {
printf("%d <-> ", current->data);
current = current->prev;
} while (current != list->tail);
printf("(back to tail)\n");
}

---

Complete Demo Program

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Include all the function definitions from above here
// [All previous function implementations would go here]
int main() {
CircularList list;
initList(&list);
printf("=== CIRCULAR LINKED LIST DEMO ===\n\n");
// Insertion operations
printf("--- Insertion Operations ---\n");
insertAtBeginning(&list, 10);
insertAtBeginning(&list, 5);
insertAtEnd(&list, 20);
insertAtEnd(&list, 25);
insertAtPosition(&list, 15, 2);
insertAfterValue(&list, 20, 22);
displayList(&list);
printf("\n");
// Search operations
printf("--- Search Operations ---\n");
searchValue(&list, 15);
searchValue(&list, 100);
Node* node = getNodeAtPosition(&list, 3);
if (node) {
printf("Node at position 3: %d\n\n", node->data);
}
// Display with positions
displayWithPositions(&list);
printf("\n");
// Deletion operations
printf("--- Deletion Operations ---\n");
deleteFromBeginning(&list);
displayList(&list);
deleteFromEnd(&list);
displayList(&list);
deleteByValue(&list, 15);
displayList(&list);
deleteFromPosition(&list, 1);
displayList(&list);
printf("\n");
// Reverse and rotate
printf("--- Advanced Operations ---\n");
insertAtEnd(&list, 30);
insertAtEnd(&list, 35);
insertAtEnd(&list, 40);
printf("Original: ");
displayList(&list);
reverseList(&list);
printf("Reversed: ");
displayList(&list);
rotateList(&list, 2);
printf("Rotated by 2: ");
displayList(&list);
printf("\n");
// Split and merge demonstration
printf("--- Split and Merge ---\n");
CircularList list1, list2, merged;
// Create sorted lists for merge demo
insertAtEnd(&list1, 10);
insertAtEnd(&list1, 30);
insertAtEnd(&list1, 50);
insertAtEnd(&list2, 20);
insertAtEnd(&list2, 40);
insertAtEnd(&list2, 60);
printf("List1: ");
displayList(&list1);
printf("List2: ");
displayList(&list2);
mergeSortedLists(&list1, &list2, &merged);
printf("Merged: ");
displayList(&merged);
printf("\n");
// Josephus problem
printf("--- Josephus Problem ---\n");
josephusProblem(7, 3);
printf("\n");
// Doubly circular linked list demo
printf("--- DOUBLY CIRCULAR LINKED LIST ---\n");
DoublyCircularList dlist;
initDoublyList(&dlist);
insertAtBeginningDoubly(&dlist, 10);
insertAtBeginningDoubly(&dlist, 5);
insertAtEndDoubly(&dlist, 20);
insertAtEndDoubly(&dlist, 25);
displayForward(&dlist);
displayBackward(&dlist);
// Clean up
freeList(&list);
// Note: Add free function for doubly circular list
return 0;
}

---

Time Complexity Analysis

Operation	Time Complexity	Description
Insert at beginning	O(1)	Constant time
Insert at end	O(1)	Constant time (with tail pointer)
Insert at position	O(n)	Need to traverse to position
Delete from beginning	O(1)	Constant time
Delete from end	O(n)	Need to traverse to previous node
Delete by value	O(n)	Need to find the node
Search	O(n)	Linear search
Traversal	O(n)	Visit all nodes
Reverse	O(n)	Traverse and update pointers

---

Advantages and Disadvantages

Advantages

1. Circular traversal - Can traverse infinitely
2. No NULL references - Every node points to another node
3. Efficient for circular operations - Round-robin, Josephus problem
4. Can be used as circular buffer - Fixed-size circular storage
5. Easy to implement round-robin - Process scheduling

Disadvantages

1. Complexity - Slightly more complex than singly linked list
2. Infinite loop risk - Need careful termination conditions
3. Memory overhead - Extra pointer per node
4. More complex debugging - Circular references can be tricky

---

Common Applications

1. Round-robin scheduling - Operating systems
2. Circular buffers - Data streaming
3. Josephus problem - Mathematical problems
4. Multiplayer game loops - Turn-based games
5. Music playlists - Repeat mode
6. Token ring networks - Network protocols
7. Cache implementation - Circular cache
8. Undo/Redo functionality - Limited history

---

Best Practices

1. Always maintain circular property - After every operation
2. Handle empty list properly - Special case when size = 0
3. Update tail pointer efficiently - For O(1) end operations
4. Check for NULL after malloc - Memory allocation validation
5. Free memory properly - Avoid memory leaks
6. Use size variable - For O(1) size queries
7. Be careful with termination - Avoid infinite loops

---

Conclusion

Circular linked lists are powerful data structures that excel in scenarios requiring cyclic traversal. Key takeaways:

• Circular property enables infinite traversal
• Efficient for specific applications like round-robin scheduling
• Both singly and doubly circular variants available
• Josephus problem demonstrates practical application
• Careful implementation required to maintain circular nature

This comprehensive implementation provides all essential operations for both singly and doubly circular linked lists, along with advanced features like splitting, merging, and the classic Josephus problem solution.