Data Structures & AlgorithmsCircular Linked Lists

Circular Linked Lists

LevelIntermediate

Duration55 mins

TopicCircular Linked Lists

3 / 4

Use Cases — Round-Robin Scheduling, Circular Buffers

From Theory to Practice

Understanding a data structure's mechanics is only half the battle. The real test of mastery is recognizing when and why to use it in practice. Circular linked lists aren't just an academic curiosity—they power critical systems that you interact with every day, often without realizing it.

When your operating system gives each running program a fair slice of CPU time, it's likely using concepts that map perfectly to circular linked lists. When your keyboard buffers keystrokes while you type faster than the computer can process, or when a streaming service maintains a playback buffer, circular structures are at work.

This page bridges theory and practice. We'll explore the most important real-world applications of circular linked lists, understanding not just how they work, but why circular structures are the natural fit for these problems.

What You Will Master

By the end of this page, you will deeply understand how circular linked lists solve real problems in operating systems, embedded systems, networking, and applications. You'll see complete implementations of round-robin schedulers and circular buffers, and you'll develop intuition for recognizing when circular structures are the right choice.

Round-Robin Scheduling — The Concept

Round-robin scheduling is a fundamental algorithm used in operating systems, task schedulers, and load balancers. The idea is simple: give each participant (process, task, server) an equal turn, cycling through all participants indefinitely.

The Core Problem:

Imagine an operating system running five programs simultaneously. The CPU can only execute one program at a time, so the OS must decide which program runs and for how long. A fair approach gives each program a small time slice (called a quantum), then moves to the next program, cycling through all of them repeatedly.

Why Circular Lists Are a Natural Fit:

Consider modeling this with a linear linked list:

head → [P1] → [P2] → [P3] → [P4] → [P5] → null

After executing P5, we need to go back to P1. With a linear list, we'd have to reset our pointer to the head manually. With a circular list:

     → [P1] → [P2] → [P3] → [P4] → [P5] ─┐
     ↑                                    │
     └────────────────────────────────────┘

After P5, following next naturally brings us to P1. The data structure embodies the cyclic semantics of the problem. No special case logic is needed; the wraparound is inherent.

The Beauty of Semantic Alignment

When your data structure aligns with your problem's semantics, code becomes simpler and bugs become fewer. Round-robin scheduling is inherently cyclic—using a circular data structure means the code reflects the algorithm's logic directly.

Implementing a Round-Robin Scheduler

Let's build a complete round-robin scheduler using a circular linked list. This implementation supports:

Adding new tasks dynamically
Removing completed tasks
Getting the next task to run
Cycling through all tasks indefinitely

We'll use a singly circular list since we only need forward traversal.

Round-Robin Scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Task representation
interface Task {
    id: string;
    name: string;
    remainingTime: number; // Time units remaining
}
 
// Node for the scheduler
class SchedulerNode {
    task: Task;
    next: SchedulerNode;
    
    constructor(task: Task) {
        this.task = task;
        this.next = this; // Self-referential for single node
    }
}
 
// Round-Robin Scheduler using Circular Linked List
class RoundRobinScheduler {
    private current: SchedulerNode | null;
    private taskCount: number;
    private timeQuantum: number;
    
    constructor(timeQuantum: number = 10) {
        this.current = null;
        this.taskCount = 0;
        this.timeQuantum = timeQuantum;
    }
    
    // Add a new task to the scheduler: O(1)
    addTask(task: Task): void {
        const newNode = new SchedulerNode(task);
        
        if (this.current === null) {
            // First task: point to itself
            this.current = newNode;
        } else {
            // Insert after current, so it gets scheduled soon
            newNode.next = this.current.next;
            this.current.next = newNode;
        }
        
        this.taskCount++;
        console.log(`Added task: ${task.name} (ID: ${task.id})`);
    }
    
    // Remove a completed task: O(n) to find predecessor
    removeTask(taskId: string): boolean {
        if (this.current === null) return false;
        
        // Find the node to remove and its predecessor
        let prev = this.current;
        let toRemove: SchedulerNode | null = null;
        let found = false;
        
        // Search through the circular list
        do {
            if (prev.next.task.id === taskId) {
                toRemove = prev.next;
                found = true;
                break;
            }
            prev = prev.next;
        } while (prev !== this.current);
        
        if (!found || !toRemove) return false;
        
        if (toRemove === toRemove.next) {
            // Only one task remaining
            this.current = null;
        } else {
            // Remove from list
            prev.next = toRemove.next;
            // If we removed current, advance current
            if (toRemove === this.current) {
                this.current = prev.next;
            }
        }
        
        this.taskCount--;
        console.log(`Removed task: ${toRemove.task.name}`);
        return true;
    }
    
    // Get the next task to execute and advance: O(1)
    getNextTask(): Task | null {
        if (this.current === null) return null;
        
        const task = this.current.task;
        this.current = this.current.next; // Advance to next
        return task;
    }
    
    // Simulate running the scheduler for a given number of cycles
    run(maxCycles: number): void {
        console.log(`\nStarting Round-Robin Scheduler (Quantum: ${this.timeQuantum} units)\n`);
        
        let cycle = 0;
        
        while (this.taskCount > 0 && cycle < maxCycles) {
            const task = this.getNextTask();
            if (!task) break;
            
            // Execute task for one quantum
            const executeTime = Math.min(this.timeQuantum, task.remainingTime);
            task.remainingTime -= executeTime;
            
            console.log(`Cycle ${cycle + 1}: Running ${task.name} for ${executeTime} units. Remaining: ${task.remainingTime}`);
            
            // If task is complete, remove it
            if (task.remainingTime <= 0) {
                this.removeTask(task.id);
            }
            
            cycle++;
        }
        
        console.log(`\nScheduler finished after ${cycle} cycles. Tasks remaining: ${this.taskCount}`);
    }
    
    // Display all tasks in the scheduler
    displayTasks(): void {
        if (this.current === null) {
            console.log("No tasks in scheduler");
            return;
        }
        
        const tasks: string[] = [];
        let node = this.current;
        
        do {
            tasks.push(`${node.task.name}(${node.task.remainingTime})`);
            node = node.next;
        } while (node !== this.current);
        
        console.log("Tasks: " + tasks.join(" → ") + " → (cycle)");
    }
}
 
// Example usage
const scheduler = new RoundRobinScheduler(10);
 
scheduler.addTask({ id: "1", name: "Browser", remainingTime: 25 });
scheduler.addTask({ id: "2", name: "Music", remainingTime: 15 });
scheduler.addTask({ id: "3", name: "Download", remainingTime: 30 });
scheduler.addTask({ id: "4", name: "Antivirus", remainingTime: 10 });
 
console.log("\nInitial state:");
scheduler.displayTasks();
 
scheduler.run(20);

Key Insight

Notice how the scheduler naturally cycles through tasks by just calling getNextTask() and advancing the current pointer. There's no 'if at end, go back to start' logic—the circular structure handles it automatically. This is the power of semantic alignment between data structure and problem.

Circular Buffers — The Concept

A circular buffer (also called a ring buffer) is a fixed-size data structure that uses a single buffer as if it were connected end-to-end. When the buffer fills up and new data arrives, it overwrites the oldest data.

The Core Problem:

Imagine you're building a system that logs the last 1000 events. You could use a regular array and shift elements when it fills up (O(n) per insertion), or you could allocate a new array each time you run out of space. Both approaches are inefficient.

A circular buffer provides a better solution: maintain two pointers—one for reading (head) and one for writing (tail)—and let them wrap around when they reach the end of the buffer.

Why Circular Structures Fit:

The wraparound behavior is exactly what circular linked lists model naturally. While circular buffers are often implemented with arrays (for memory locality), the conceptual model is circular, and linked list implementations are valuable when:

Buffer size needs to change dynamically
Elements are complex objects that shouldn't be moved
The buffer is part of a larger linked structure

Circular Buffer Applications
Application	Why Circular Buffer?	Example
Keyboard Input Buffer	Stores keystrokes until processed; old keys dropped if buffer full	Typing faster than CPU processes
Audio/Video Streaming	Maintains playback buffer; overwrites oldest frames	Netflix, Spotify buffering
Logging Systems	Keeps last N log entries without unbounded growth	System logs, debugging traces
Network Packet Queues	Handles burst traffic; drops oldest packets if overwhelmed	Router packet buffers
Sensor Data Collection	Stores recent readings without memory exhaustion	IoT devices, wearables
Undo/Redo History	Maintains last N actions; discards oldest	Text editors, design tools

Array vs. Linked List Implementation

Most circular buffers in practice use arrays with modular arithmetic for index wraparound. This offers better cache locality. Linked list implementations are preferred when elements are large, the buffer size varies, or the circular buffer is integrated with other node-based structures.

Implementing a Circular Buffer with Linked List

Let's implement a circular buffer using a circular linked list. This implementation:

Maintains a fixed maximum capacity
Overwrites oldest data when full
Provides O(1) read and write operations
Supports iteration through all elements in order

Circular Buffer with Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// Node for the circular buffer
class BufferNode<T> {
    data: T | null;
    next: BufferNode<T>;
    
    constructor() {
        this.data = null;
        this.next = this;
    }
}
 
// Circular Buffer using Circular Linked List
class CircularBuffer<T> {
    private head: BufferNode<T>;  // Read position
    private tail: BufferNode<T>;  // Write position
    private capacity: number;
    private count: number;        // Current number of elements
    
    constructor(capacity: number) {
        if (capacity < 1) {
            throw new Error("Capacity must be at least 1");
        }
        
        this.capacity = capacity;
        this.count = 0;
        
        // Pre-allocate all nodes in a circular chain
        this.head = new BufferNode<T>();
        let current = this.head;
        
        for (let i = 1; i < capacity; i++) {
            const newNode = new BufferNode<T>();
            current.next = newNode;
            current = newNode;
        }
        
        // Complete the circle
        current.next = this.head;
        this.tail = this.head;
    }
    
    // Check if buffer is empty
    isEmpty(): boolean {
        return this.count === 0;
    }
    
    // Check if buffer is full
    isFull(): boolean {
        return this.count === this.capacity;
    }
    
    // Get current number of elements
    size(): number {
        return this.count;
    }
    
    // Write data to the buffer: O(1)
    write(data: T): boolean {
        let overwritten = false;
        
        // If buffer is full, we're overwriting oldest data
        if (this.isFull()) {
            overwritten = true;
            // Move head forward (lose oldest element)
            this.head = this.head.next;
        } else {
            this.count++;
        }
        
        // Write data at tail position
        this.tail.data = data;
        // Advance tail
        this.tail = this.tail.next;
        
        return overwritten; // Returns true if old data was overwritten
    }
    
    // Read and remove oldest data: O(1)
    read(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        
        const data = this.head.data;
        this.head.data = null; // Clear the slot
        this.head = this.head.next;
        this.count--;
        
        return data;
    }
    
    // Peek at oldest data without removing: O(1)
    peek(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        return this.head.data;
    }
    
    // Get all elements in order (oldest to newest)
    toArray(): T[] {
        const result: T[] = [];
        
        if (this.isEmpty()) {
            return result;
        }
        
        let current = this.head;
        let counted = 0;
        
        while (counted < this.count) {
            if (current.data !== null) {
                result.push(current.data);
            }
            current = current.next;
            counted++;
        }
        
        return result;
    }
    
    // Display buffer state
    display(): void {
        const elements = this.toArray();
        console.log(`Buffer [${this.count}/${this.capacity}]: ${elements.join(" → ") || "(empty)"}`);
    }
}
 
// Example: Event logging with circular buffer
console.log("=== Event Logger Example ===\n");
 
const eventLog = new CircularBuffer<string>(5);
 
// Log some events
eventLog.write("User logged in");
eventLog.write("File opened");
eventLog.write("File saved");
eventLog.display();
 
// Fill the buffer
eventLog.write("Email sent");
eventLog.write("File closed");
eventLog.display();
 
// Now buffer is full. New writes will overwrite oldest
console.log("\nBuffer is full. Adding more events...");
eventLog.write("User logged out"); // Overwrites "User logged in"
eventLog.display();
 
eventLog.write("System shutdown"); // Overwrites "File opened"
eventLog.display();
 
// Read oldest event
console.log(`\nReading oldest: ${eventLog.read()}`);
eventLog.display();

Memory Consideration

This implementation pre-allocates all nodes upfront. This is intentional—it ensures consistent memory usage regardless of fill level. For large buffers with large objects, consider lazy allocation or using arrays instead.

The Josephus Problem — A Classic Application

The Josephus Problem is a theoretical problem in computer science and mathematics named after the historian Flavius Josephus. While historically significant, it's also an excellent demonstration of circular linked lists in action.

The Problem:

N people stand in a circle. Starting from a designated first person, you count around the circle k people. The k-th person is eliminated from the circle. Then, starting from the next person, you count k people again, and eliminate the k-th. This continues until only one person remains. The question: which position survives?

Why Circular Lists?

This is perhaps the most natural application of circular linked lists:

People naturally form a circle → circular structure
We need to traverse repeatedly → infinite traversal
We need to remove elements from arbitrary positions → linked list operations
After removal, we continue from the next person → natural with linked lists

Josephus Problem Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Solve the Josephus Problem using a circular linked list
function josephus(n: number, k: number): number {
    if (n < 1 || k < 1) {
        throw new Error("n and k must be positive integers");
    }
    
    // Create circular linked list of n people (numbered 1 to n)
    class PersonNode {
        position: number;
        next: PersonNode;
        
        constructor(position: number) {
            this.position = position;
            this.next = this;
        }
    }
    
    // Build the circle
    const head = new PersonNode(1);
    let current = head;
    
    for (let i = 2; i <= n; i++) {
        const newPerson = new PersonNode(i);
        current.next = newPerson;
        current = newPerson;
    }
    
    // Complete the circle
    current.next = head;
    
    // We need to track the node BEFORE the one to be eliminated
    let prev = current; // Points to node n
    current = head;     // Points to node 1
    
    // Simulate the elimination process
    const eliminationOrder: number[] = [];
    
    while (current.next !== current) {
        // Count k-1 steps (stop at the node before the k-th)
        for (let count = 1; count < k; count++) {
            prev = current;
            current = current.next;
        }
        
        // Eliminate current (the k-th person)
        eliminationOrder.push(current.position);
        prev.next = current.next; // Remove current from circle
        current = prev.next;      // Move to next person
    }
    
    // The last remaining person
    const survivor = current.position;
    eliminationOrder.push(survivor);
    
    console.log(`Elimination order: ${eliminationOrder.slice(0, -1).join(" → ")}`);
    console.log(`Survivor: Position ${survivor}`);
    
    return survivor;
}
 
// Examples
console.log("=== Josephus Problem ===\n");
 
console.log("Example 1: n=7, k=3");
josephus(7, 3);
 
console.log("\nExample 2: n=5, k=2");
josephus(5, 2);
 
console.log("\nExample 3: n=10, k=4");
josephus(10, 4);

Complexity Analysis

This simulation runs in O(n × k) time—we eliminate n-1 people, and for each elimination, we take k steps. For small k, this is essentially O(n). Mathematical formulas exist for O(n) or even O(log n) solutions, but the circular list simulation is intuitive and demonstrates the data structure perfectly.

Additional Use Cases

Beyond round-robin scheduling, circular buffers, and the Josephus problem, circular linked lists appear in many other contexts. Let's explore several more applications:

More Applications of Circular Linked Lists

•Music/Video Playlist Looping — When 'repeat all' is enabled, the last track's 'next' is the first track. Circular lists model this directly. Shuffle can work too—just randomize the circular order once.
•Token Ring Networks — In this network topology, a special token circulates among nodes. Only the node holding the token can transmit. The network is literally a ring—a circular linked list of network nodes.
•Game Turn Management — In multiplayer games where turns rotate, a circular list of players eliminates edge-case handling. When a player leaves, they're simply removed from the circle.
•Carousel/Slideshow UIs — Image carousels that loop infinitely map naturally to circular lists. The 'previous' on the first slide goes to the last, and 'next' on the last goes to the first.
•CPU Instruction Pipelines — Modern CPUs use circular buffers for instruction queues, reorder buffers, and similar structures. The circular nature helps manage instruction flow efficiently.
•Memory Pool Management — Fixed-size memory pools can use circular lists to track free blocks. Allocations and deallocations become O(1) list operations.
•Hot Key Rotation — Features like 'cycle through open windows' (Alt+Tab) use circular lists. Each press advances to the next element, wrapping at the end.

The Common Thread:

All these applications share key characteristics:

Cyclic nature — The sequence repeats or wraps around
No natural termination — There's no end to the sequence in a structural sense
Equal treatment of elements — No element is inherently 'first' or 'last'
Continuous processing — Operations continue indefinitely, cycling through elements

When you encounter a problem with these characteristics, circular linked lists should immediately come to mind as a candidate data structure.

Recognition Pattern

When a problem description uses words like 'cycle,' 'rotate,' 'loop back,' 'repeat,' 'wrap around,' or 'circular'—pause and consider whether a circular linked list would be a natural fit. The vocabulary of the problem often hints at the right data structure.

Summary: Circular Linked Lists in Practice

We've explored the key real-world applications of circular linked lists. Let's consolidate the insights:

Key Takeaways

•Round-Robin Scheduling — Fair CPU allocation by cycling through processes. Circular lists eliminate wraparound logic; the structure naturally cycles.
•Circular Buffers — Fixed-size buffers with overwrite-on-full semantics. Perfect for logging, streaming, and bounded queues.
•Josephus Problem — Classic elimination game in a circle. Circular lists enable direct simulation with simple pointer manipulation.
•Semantic Alignment — Using circular structures for circular problems simplifies code and reduces bugs. The data structure should reflect the problem's nature.
•Implementation Flexibility — Circular buffers can use arrays or linked lists depending on needs. Linked lists shine when size varies or elements are large.
•Pattern Recognition — Look for cyclic, looping, rotating, or wrap-around behavior in problems. These are signals that circular structures may be appropriate.
•Real-World Prevalence — From operating systems to networking to user interfaces, circular structures appear throughout computer science.

What's Next:

Now that you understand the applications of circular linked lists, there's one critical challenge remaining: detecting the end condition. Unlike linear lists where null signals termination, circular lists require different approaches to know when we've traversed all elements. The next page explores this challenge in depth.

Page Complete

You now understand the major real-world applications of circular linked lists. You've seen complete implementations of round-robin schedulers, circular buffers, and the Josephus problem. You can recognize when circular structures are appropriate and implement them for your own use cases.

3 / 4

Loading learning content...

Data Structures & AlgorithmsCircular Linked Lists

Circular Linked Lists

LevelIntermediate

Duration55 mins

TopicCircular Linked Lists

3 / 4

Use Cases — Round-Robin Scheduling, Circular Buffers

From Theory to Practice

What You Will Master

Round-Robin Scheduling — The Concept

The Core Problem:

Why Circular Lists Are a Natural Fit:

Consider modeling this with a linear linked list:

head → [P1] → [P2] → [P3] → [P4] → [P5] → null

After executing P5, we need to go back to P1. With a linear list, we'd have to reset our pointer to the head manually. With a circular list:

     → [P1] → [P2] → [P3] → [P4] → [P5] ─┐
     ↑                                    │
     └────────────────────────────────────┘

After P5, following next naturally brings us to P1. The data structure embodies the cyclic semantics of the problem. No special case logic is needed; the wraparound is inherent.

The Beauty of Semantic Alignment

Implementing a Round-Robin Scheduler

Let's build a complete round-robin scheduler using a circular linked list. This implementation supports:

Adding new tasks dynamically
Removing completed tasks
Getting the next task to run
Cycling through all tasks indefinitely

We'll use a singly circular list since we only need forward traversal.

Round-Robin Scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Task representation
interface Task {
    id: string;
    name: string;
    remainingTime: number; // Time units remaining
}
 
// Node for the scheduler
class SchedulerNode {
    task: Task;
    next: SchedulerNode;
    
    constructor(task: Task) {
        this.task = task;
        this.next = this; // Self-referential for single node
    }
}
 
// Round-Robin Scheduler using Circular Linked List
class RoundRobinScheduler {
    private current: SchedulerNode | null;
    private taskCount: number;
    private timeQuantum: number;
    
    constructor(timeQuantum: number = 10) {
        this.current = null;
        this.taskCount = 0;
        this.timeQuantum = timeQuantum;
    }
    
    // Add a new task to the scheduler: O(1)
    addTask(task: Task): void {
        const newNode = new SchedulerNode(task);
        
        if (this.current === null) {
            // First task: point to itself
            this.current = newNode;
        } else {
            // Insert after current, so it gets scheduled soon
            newNode.next = this.current.next;
            this.current.next = newNode;
        }
        
        this.taskCount++;
        console.log(`Added task: ${task.name} (ID: ${task.id})`);
    }
    
    // Remove a completed task: O(n) to find predecessor
    removeTask(taskId: string): boolean {
        if (this.current === null) return false;
        
        // Find the node to remove and its predecessor
        let prev = this.current;
        let toRemove: SchedulerNode | null = null;
        let found = false;
        
        // Search through the circular list
        do {
            if (prev.next.task.id === taskId) {
                toRemove = prev.next;
                found = true;
                break;
            }
            prev = prev.next;
        } while (prev !== this.current);
        
        if (!found || !toRemove) return false;
        
        if (toRemove === toRemove.next) {
            // Only one task remaining
            this.current = null;
        } else {
            // Remove from list
            prev.next = toRemove.next;
            // If we removed current, advance current
            if (toRemove === this.current) {
                this.current = prev.next;
            }
        }
        
        this.taskCount--;
        console.log(`Removed task: ${toRemove.task.name}`);
        return true;
    }
    
    // Get the next task to execute and advance: O(1)
    getNextTask(): Task | null {
        if (this.current === null) return null;
        
        const task = this.current.task;
        this.current = this.current.next; // Advance to next
        return task;
    }
    
    // Simulate running the scheduler for a given number of cycles
    run(maxCycles: number): void {
        console.log(`\nStarting Round-Robin Scheduler (Quantum: ${this.timeQuantum} units)\n`);
        
        let cycle = 0;
        
        while (this.taskCount > 0 && cycle < maxCycles) {
            const task = this.getNextTask();
            if (!task) break;
            
            // Execute task for one quantum
            const executeTime = Math.min(this.timeQuantum, task.remainingTime);
            task.remainingTime -= executeTime;
            
            console.log(`Cycle ${cycle + 1}: Running ${task.name} for ${executeTime} units. Remaining: ${task.remainingTime}`);
            
            // If task is complete, remove it
            if (task.remainingTime <= 0) {
                this.removeTask(task.id);
            }
            
            cycle++;
        }
        
        console.log(`\nScheduler finished after ${cycle} cycles. Tasks remaining: ${this.taskCount}`);
    }
    
    // Display all tasks in the scheduler
    displayTasks(): void {
        if (this.current === null) {
            console.log("No tasks in scheduler");
            return;
        }
        
        const tasks: string[] = [];
        let node = this.current;
        
        do {
            tasks.push(`${node.task.name}(${node.task.remainingTime})`);
            node = node.next;
        } while (node !== this.current);
        
        console.log("Tasks: " + tasks.join(" → ") + " → (cycle)");
    }
}
 
// Example usage
const scheduler = new RoundRobinScheduler(10);
 
scheduler.addTask({ id: "1", name: "Browser", remainingTime: 25 });
scheduler.addTask({ id: "2", name: "Music", remainingTime: 15 });
scheduler.addTask({ id: "3", name: "Download", remainingTime: 30 });
scheduler.addTask({ id: "4", name: "Antivirus", remainingTime: 10 });
 
console.log("\nInitial state:");
scheduler.displayTasks();
 
scheduler.run(20);

Key Insight

Circular Buffers — The Concept

The Core Problem:

A circular buffer provides a better solution: maintain two pointers—one for reading (head) and one for writing (tail)—and let them wrap around when they reach the end of the buffer.

Why Circular Structures Fit:

Buffer size needs to change dynamically
Elements are complex objects that shouldn't be moved
The buffer is part of a larger linked structure

Circular Buffer Applications
Application	Why Circular Buffer?	Example
Keyboard Input Buffer	Stores keystrokes until processed; old keys dropped if buffer full	Typing faster than CPU processes
Audio/Video Streaming	Maintains playback buffer; overwrites oldest frames	Netflix, Spotify buffering
Logging Systems	Keeps last N log entries without unbounded growth	System logs, debugging traces
Network Packet Queues	Handles burst traffic; drops oldest packets if overwhelmed	Router packet buffers
Sensor Data Collection	Stores recent readings without memory exhaustion	IoT devices, wearables
Undo/Redo History	Maintains last N actions; discards oldest	Text editors, design tools

Array vs. Linked List Implementation

Implementing a Circular Buffer with Linked List

Let's implement a circular buffer using a circular linked list. This implementation:

Maintains a fixed maximum capacity
Overwrites oldest data when full
Provides O(1) read and write operations
Supports iteration through all elements in order

Circular Buffer with Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// Node for the circular buffer
class BufferNode<T> {
    data: T | null;
    next: BufferNode<T>;
    
    constructor() {
        this.data = null;
        this.next = this;
    }
}
 
// Circular Buffer using Circular Linked List
class CircularBuffer<T> {
    private head: BufferNode<T>;  // Read position
    private tail: BufferNode<T>;  // Write position
    private capacity: number;
    private count: number;        // Current number of elements
    
    constructor(capacity: number) {
        if (capacity < 1) {
            throw new Error("Capacity must be at least 1");
        }
        
        this.capacity = capacity;
        this.count = 0;
        
        // Pre-allocate all nodes in a circular chain
        this.head = new BufferNode<T>();
        let current = this.head;
        
        for (let i = 1; i < capacity; i++) {
            const newNode = new BufferNode<T>();
            current.next = newNode;
            current = newNode;
        }
        
        // Complete the circle
        current.next = this.head;
        this.tail = this.head;
    }
    
    // Check if buffer is empty
    isEmpty(): boolean {
        return this.count === 0;
    }
    
    // Check if buffer is full
    isFull(): boolean {
        return this.count === this.capacity;
    }
    
    // Get current number of elements
    size(): number {
        return this.count;
    }
    
    // Write data to the buffer: O(1)
    write(data: T): boolean {
        let overwritten = false;
        
        // If buffer is full, we're overwriting oldest data
        if (this.isFull()) {
            overwritten = true;
            // Move head forward (lose oldest element)
            this.head = this.head.next;
        } else {
            this.count++;
        }
        
        // Write data at tail position
        this.tail.data = data;
        // Advance tail
        this.tail = this.tail.next;
        
        return overwritten; // Returns true if old data was overwritten
    }
    
    // Read and remove oldest data: O(1)
    read(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        
        const data = this.head.data;
        this.head.data = null; // Clear the slot
        this.head = this.head.next;
        this.count--;
        
        return data;
    }
    
    // Peek at oldest data without removing: O(1)
    peek(): T | null {
        if (this.isEmpty()) {
            return null;
        }
        return this.head.data;
    }
    
    // Get all elements in order (oldest to newest)
    toArray(): T[] {
        const result: T[] = [];
        
        if (this.isEmpty()) {
            return result;
        }
        
        let current = this.head;
        let counted = 0;
        
        while (counted < this.count) {
            if (current.data !== null) {
                result.push(current.data);
            }
            current = current.next;
            counted++;
        }
        
        return result;
    }
    
    // Display buffer state
    display(): void {
        const elements = this.toArray();
        console.log(`Buffer [${this.count}/${this.capacity}]: ${elements.join(" → ") || "(empty)"}`);
    }
}
 
// Example: Event logging with circular buffer
console.log("=== Event Logger Example ===\n");
 
const eventLog = new CircularBuffer<string>(5);
 
// Log some events
eventLog.write("User logged in");
eventLog.write("File opened");
eventLog.write("File saved");
eventLog.display();
 
// Fill the buffer
eventLog.write("Email sent");
eventLog.write("File closed");
eventLog.display();
 
// Now buffer is full. New writes will overwrite oldest
console.log("\nBuffer is full. Adding more events...");
eventLog.write("User logged out"); // Overwrites "User logged in"
eventLog.display();
 
eventLog.write("System shutdown"); // Overwrites "File opened"
eventLog.display();
 
// Read oldest event
console.log(`\nReading oldest: ${eventLog.read()}`);
eventLog.display();

Memory Consideration

The Josephus Problem — A Classic Application

The Problem:

Why Circular Lists?

This is perhaps the most natural application of circular linked lists:

People naturally form a circle → circular structure
We need to traverse repeatedly → infinite traversal
We need to remove elements from arbitrary positions → linked list operations
After removal, we continue from the next person → natural with linked lists

Josephus Problem Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Solve the Josephus Problem using a circular linked list
function josephus(n: number, k: number): number {
    if (n < 1 || k < 1) {
        throw new Error("n and k must be positive integers");
    }
    
    // Create circular linked list of n people (numbered 1 to n)
    class PersonNode {
        position: number;
        next: PersonNode;
        
        constructor(position: number) {
            this.position = position;
            this.next = this;
        }
    }
    
    // Build the circle
    const head = new PersonNode(1);
    let current = head;
    
    for (let i = 2; i <= n; i++) {
        const newPerson = new PersonNode(i);
        current.next = newPerson;
        current = newPerson;
    }
    
    // Complete the circle
    current.next = head;
    
    // We need to track the node BEFORE the one to be eliminated
    let prev = current; // Points to node n
    current = head;     // Points to node 1
    
    // Simulate the elimination process
    const eliminationOrder: number[] = [];
    
    while (current.next !== current) {
        // Count k-1 steps (stop at the node before the k-th)
        for (let count = 1; count < k; count++) {
            prev = current;
            current = current.next;
        }
        
        // Eliminate current (the k-th person)
        eliminationOrder.push(current.position);
        prev.next = current.next; // Remove current from circle
        current = prev.next;      // Move to next person
    }
    
    // The last remaining person
    const survivor = current.position;
    eliminationOrder.push(survivor);
    
    console.log(`Elimination order: ${eliminationOrder.slice(0, -1).join(" → ")}`);
    console.log(`Survivor: Position ${survivor}`);
    
    return survivor;
}
 
// Examples
console.log("=== Josephus Problem ===\n");
 
console.log("Example 1: n=7, k=3");
josephus(7, 3);
 
console.log("\nExample 2: n=5, k=2");
josephus(5, 2);
 
console.log("\nExample 3: n=10, k=4");
josephus(10, 4);

Complexity Analysis

Additional Use Cases

Beyond round-robin scheduling, circular buffers, and the Josephus problem, circular linked lists appear in many other contexts. Let's explore several more applications:

More Applications of Circular Linked Lists

•Music/Video Playlist Looping — When 'repeat all' is enabled, the last track's 'next' is the first track. Circular lists model this directly. Shuffle can work too—just randomize the circular order once.
•Token Ring Networks — In this network topology, a special token circulates among nodes. Only the node holding the token can transmit. The network is literally a ring—a circular linked list of network nodes.
•Game Turn Management — In multiplayer games where turns rotate, a circular list of players eliminates edge-case handling. When a player leaves, they're simply removed from the circle.
•Carousel/Slideshow UIs — Image carousels that loop infinitely map naturally to circular lists. The 'previous' on the first slide goes to the last, and 'next' on the last goes to the first.
•CPU Instruction Pipelines — Modern CPUs use circular buffers for instruction queues, reorder buffers, and similar structures. The circular nature helps manage instruction flow efficiently.
•Memory Pool Management — Fixed-size memory pools can use circular lists to track free blocks. Allocations and deallocations become O(1) list operations.
•Hot Key Rotation — Features like 'cycle through open windows' (Alt+Tab) use circular lists. Each press advances to the next element, wrapping at the end.

The Common Thread:

All these applications share key characteristics:

Cyclic nature — The sequence repeats or wraps around
No natural termination — There's no end to the sequence in a structural sense
Equal treatment of elements — No element is inherently 'first' or 'last'
Continuous processing — Operations continue indefinitely, cycling through elements

When you encounter a problem with these characteristics, circular linked lists should immediately come to mind as a candidate data structure.

Recognition Pattern

Summary: Circular Linked Lists in Practice

We've explored the key real-world applications of circular linked lists. Let's consolidate the insights:

Key Takeaways

•Round-Robin Scheduling — Fair CPU allocation by cycling through processes. Circular lists eliminate wraparound logic; the structure naturally cycles.
•Circular Buffers — Fixed-size buffers with overwrite-on-full semantics. Perfect for logging, streaming, and bounded queues.
•Josephus Problem — Classic elimination game in a circle. Circular lists enable direct simulation with simple pointer manipulation.
•Semantic Alignment — Using circular structures for circular problems simplifies code and reduces bugs. The data structure should reflect the problem's nature.
•Implementation Flexibility — Circular buffers can use arrays or linked lists depending on needs. Linked lists shine when size varies or elements are large.
•Pattern Recognition — Look for cyclic, looping, rotating, or wrap-around behavior in problems. These are signals that circular structures may be appropriate.
•Real-World Prevalence — From operating systems to networking to user interfaces, circular structures appear throughout computer science.

What's Next:

Page Complete

3 / 4