Table of Contents

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

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

Disadvantages

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

Common Applications

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

Best Practices

Always maintain circular property - After every operation
Handle empty list properly - Special case when size = 0
Update tail pointer efficiently - For O(1) end operations
Check for NULL after malloc - Memory allocation validation
Free memory properly - Avoid memory leaks
Use size variable - For O(1) size queries
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.

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

https://macronepal.com/understanding-the-c-srand-function
Explains how srand() initializes the pseudo-random number generator in C by setting a seed value. Using the same seed produces the same sequence, while time(NULL) gives different results each run.

2. C rand() Function Mechanics and Limitations

https://macronepal.com/c-rand-function-mechanics-and-limitations
Explains how rand() generates pseudo-random numbers between 0 and RAND_MAX, its deterministic nature, and limitations for security use cases.

3. C log() Function

https://macronepal.com/c-log-function-2
Covers natural logarithm calculation using <math.h> and its applications.

4. Mastering Date and Time in C

https://macronepal.com/mastering-date-and-time-in-c
Explains <time.h> functions like time(), clock(), difftime(), and struct tm.

5. Mastering time_t Type in C

https://macronepal.com/mastering-the-c-time_t-type-for-time-management
Explains time representation as seconds since Unix epoch and conversion functions.

6. C exp() Function

https://macronepal.com/c-exp-function-mechanics-and-implementation
Explains exponential function exp(x) and its scientific applications.

7. C log() Function (Alternate Guide)

https://macronepal.com/c-log-function
Comparison of log() and log10() with usage examples.

8. C log10() Function

https://macronepal.com/mastering-the-log10-function-in-c
Explains base-10 logarithm for engineering and scientific applications.

9. C tan() Function

https://macronepal.com/understanding-the-c-tan-function
Explains tangent function and radian-based calculations.

10. Random Numbers in C (Secure vs Predictable)

https://macronepal.com/mastering-c-random-numbers-for-secure-and-predictable-applications
Explains difference between rand() and secure randomness methods.

11. Free Online C Compiler

https://macronepal.com/free-online-c-code-compiler-2
Browser-based compiler for testing C programs instantly.

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

https://macronepal.com/c/mastering-functions-in-c-a-complete-guide/
Covers function structure, modular programming, and real-world usage.

Function Arguments in C

https://macronepal.com/c-function-arguments/
Explains how arguments are passed and used in function calls.

Function Parameters in C

https://macronepal.com/c-function-parameters/
Explains defining inputs for functions and matching them with arguments.

Function Declarations in C

https://macronepal.com/c-function-declarations-syntax-rules-and-best-practices/
Covers prototypes, syntax rules, and best practices.

Function Calls in C

https://macronepal.com/understanding-function-calls-in-c-syntax-mechanics-and-best-practices/
Explains execution flow and parameter handling during function calls.

Void Functions in C

https://macronepal.com/understanding-void-functions-in-c-syntax-patterns-and-best-practices/
Explains functions that do not return values.

Return Values in C

https://macronepal.com/c-return-values-mechanics-types-and-best-practices/
Explains different return types and how functions return results.

Pass-by-Value in C

https://macronepal.com/aws/understanding-pass-by-value-in-c-mechanics-implications-and-best-practices/
Explains how copies of variables are passed into functions.

Pass-by-Reference in C

https://macronepal.com/c/understanding-pass-by-reference-in-c-pointers-semantics-and-safe-practices/
Explains using pointers to modify original variables.

C strstr() Function

https://macronepal.com/aws/c-strstr-function/
Explains substring search inside strings in C.

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

https://macronepal.com/13757-2/
https://macronepal.com/13748-2/
https://macronepal.com/13747-2/
https://macronepal.com/13746-2/
https://macronepal.com/13745-2/
https://macronepal.com/13708-2/
https://macronepal.com/13707-2/
https://macronepal.com/13702-2/

Online Compilers