Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a circular linked list in C for round-robin scheduling

Round-robin scheduling is one of the oldest and most intuitive ways to share a processor among several tasks. It is the algorithm that quietly powers the multitasking behaviour of laptops in a Melbourne café, the background services running on a developer's machine in Brisbane, and the packet dispatchers inside an Australian ISP's core router. Each ready process receives a fixed time slice, then yields the CPU to the next process in the queue. When the queue ends, the scheduler wraps back to the first entry and starts again. That simple wrap-around behaviour is the conceptual heart of this article.

A linear list makes this wrap-around awkward, because the scheduler must remember the head and tail separately, and after the tail it has to reset to the head. A circular linked list makes the wrap implicit: the last node points back to the first, and traversal can continue forever without any special reset. Implementing such a structure in C gives the programmer direct control over memory and pointers, and it sharpens understanding of how an operating system or a runtime library cycles through work units.

This guide walks through the implementation step by step, from the design of a node, through insertion and deletion, to a small scheduler loop that mimics an operating-system dispatcher. Code is written in portable C, with attention to malloc, free, and pointer arithmetic. The discussion assumes familiarity with structs and basic pointers, and it stays close to patterns taught in undergraduate systems courses across Australian universities.

Along the way, the article analyses time and space complexity, contrasts the circular linked list against a simple array-based queue, and offers practical recommendations for production use. Whether you are a student at the University of Sydney preparing for a systems assignment, a hobbyist in Perth building an embedded controller, or a backend engineer at a Sydney fintech iterating on a custom job runner, the patterns here apply broadly.

The fundamentals of round-robin scheduling

Round-robin scheduling divides time into equal slices, often called quanta, and rotates work units through them in a fixed order. The technique was popularised in early time-sharing systems such as CTSS at MIT, and it remains a default choice for cooperative and preemptive schedulers in everything from Linux's CFS to a simple Arduino sketch.

In its purest form, the scheduler holds a queue of ready processes. It removes the head, runs it for one quantum, then appends it to the tail if it is still runnable. New arrivals are inserted at the tail. This pattern preserves fairness: every process gets a turn, and no process can monopolise the CPU by spawning faster than others complete.

The algorithm has several appealing properties for teaching and for small embedded targets. It is starvation-free, it is easy to reason about, and it requires only constant extra memory beyond the queue itself. Its weakness is that it ignores priorities and burst lengths; for those concerns, weighted or multilevel feedback queues are used instead. For this article, however, the unweighted variant is the right starting point because it maps cleanly onto a circular structure.

Why circular linked lists fit the model

A circular linked list is a singly or doubly linked list whose final node points back to the head instead of holding NULL. From any node, the list can be traversed indefinitely by following the next pointer. This invariant mirrors the scheduler's wrap-around rule exactly: after serving the last process, the next step returns naturally to the first.

A simple array-based queue can also model round-robin, but it needs modulo arithmetic and a separate size variable. The circular list avoids that arithmetic entirely. Insertion at the tail is O(1) if we keep a tail pointer, and rotation is simply a pointer advance. Deletion of the head, used when a process finishes mid-quantum, is also O(1).

The trade-off is that every node carries a pointer, which costs an extra word of memory per element and prevents the cache-friendly stride of a contiguous array. For a scheduler holding a few dozen processes, this overhead is irrelevant. For a million processes, an array or a slab-based ring buffer becomes the better engineering choice. Many Australian data-engineering teams, such as those at CSIRO's Data61 in Canberra, default to ring buffers for very large pipelines precisely for this reason.

For a focused implementation in C, the circular linked list strikes a balance between clarity and performance. It is also a natural bridge to richer algorithms, and the same low-level pointer reasoning explored in this Tarjan's algorithm walkthrough applies directly when reasoning about cycles in linked structures.

Designing the node and pointer structure in C

The first design decision is the shape of a node. Each node must hold the process identifier, the remaining time quantum, and a pointer to the next node. For the purposes of this article, the process identifier can be a small integer and the remaining time an unsigned short.

typedef struct node {
    int pid;
    int remaining;
    struct node *next;
} node_t;

A second decision is whether the list is singly or doubly linked. Singly linked is enough for the basic scheduler, because rotation always advances forward. A doubly linked version would allow removal of any node in O(1), which is helpful when a process is killed externally. The discussion below uses the singly linked variant for simplicity.

The list itself is represented by a single tail pointer. The head is implicit: head = tail->next. This invariant saves a variable and removes the need to update two pointers when the last element is removed. It is a pattern familiar from textbook queues, and it appears in many open-source schedulers, including toy implementations shared at Melbourne C and systems programming meetups.

Memory is allocated with malloc and freed with free as processes enter and leave. For deterministic behaviour in long-running services, a memory pool or arena can be used instead, but the standard library calls keep the code portable across Linux, macOS, and the BSD variants common in Australian university labs.

Core operations: insert, remove, and traverse

Insertion adds a new process at the tail of the circle. If the list is empty, the new node points to itself and becomes both head and tail. Otherwise, the tail's next pointer is updated to the new node, and the new node's next pointer takes the old head.

void insert(node_t **tail, node_t *new_node) {
    if (*tail == NULL) {
        new_node->next = new_node;
        *tail = new_node;
    } else {
        new_node->next = (*tail)->next;
        (*tail)->next = new_node;
        *tail = new_node;
    }
}

Removal of the head is the operation used to advance the scheduler. It returns the node that was at the head and updates the tail to keep the invariant. If the removed node was also the tail, the list becomes empty.

node_t *remove_head(node_t **tail) {
    if (*tail == NULL) return NULL;
    node_t *head = (*tail)->next;
    if (head == *tail) {
        *tail = NULL;
    } else {
        (*tail)->next = head->next;
    }
    head->next = NULL;
    return head;
}

Traversal walks from the head, following next pointers, until the original head is revisited. In a scheduler loop, the traversal is driven by the quantum rather than by a full pass. A counter or an iterator advances one step per quantum, and the loop continues until the list is empty.

These three primitives form a complete API. They are the building blocks of every more elaborate scheduler, including those that implement priority inheritance or fair queueing on top of round-robin.

Putting it together: the scheduler loop

The scheduler is a small driver function. It takes the tail of the circular list and a quantum size, and it runs until all processes report completion. Each iteration removes the head, simulates work for one quantum by decrementing its remaining time, and either reinserts it at the tail or frees it.

void run_scheduler(node_t **tail, int quantum) {
    while (*tail != NULL) {
        node_t *current = remove_head(tail);
        int slice = (current->remaining < quantum) ? current->remaining : quantum;
        current->remaining -= slice;
        if (current->remaining > 0) {
            insert(tail, current);
        } else {
            free(current);
        }
    }
}

In a real operating system the slice would be filled by a context switch, but the structure is identical. The function is short enough to reason about line by line, which is one of the reasons round-robin remains a teaching staple in subjects such as UNSW's COMP3231 and the University of Melbourne's operating systems courses.

To make the example runnable, a small main function can populate the list with a few processes and print their identifiers as they complete. For larger simulations, the same loop can be instrumented to log waiting time, turnaround time, and context switches, which are the standard metrics taught in introductory scheduling theory.

Complexity analysis and performance trade-offs

Every rotation of the scheduler performs a constant amount of work: pointer arithmetic, a decrement, and either an insertion or a free. The amortised cost per process per quantum is therefore O(1). The overall complexity for n processes over m quanta is O(n + m), which is linear in the total amount of work done.

The comparison below contrasts this implementation against an array-based circular queue and a doubly linked circular list. Each row captures a property that matters when choosing a structure for a scheduler.

Property Singly linked circle Array ring buffer Doubly linked circle
Memory per element pointer + payload payload only two pointers + payload
Insert at tail O(1) O(1) O(1)
Remove arbitrary node O(n) O(1) with index O(1)
Cache locality poor excellent poor
Code complexity low medium medium
Failure modes dangling pointer index overflow dangling pointer

For most teaching and small-scale projects the singly linked variant wins on clarity. For production systems that handle tens of thousands of processes, the array ring buffer is the better choice because of its cache behaviour and predictable memory layout. The doubly linked circle is the right answer when processes are frequently killed by external signals, such as in a long-running batch controller used by mining analytics teams in Perth.

Practical extensions and recommendations

The basic scheduler above is intentionally minimal. Real systems add priorities, accounting, and avoidance of priority inversion. The list below collects the most useful directions to take next, drawn from common patterns in Australian engineering teams and university curricula.