Implementing a Circular Doubly Linked List in C

A circular doubly linked list combines two useful properties: every node stores links in both directions, and the final node points back to the first. There is no NULL link at either end. This makes the structure useful for round-robin scheduling, rotating menus, playlist navigation, and queues that repeatedly cycle through available items. Learn more about Understanding The Gaussian Mixture Models For Clustering.

In C, the design requires careful pointer manipulation and explicit memory management. A reliable implementation starts with clear invariants, uses a sentinel node to simplify edge cases, and exposes operations that preserve the list’s structure after insertion, deletion, and traversal.

Why Use A Circular Structure

A conventional doubly linked list usually has head->prev == NULL and tail->next == NULL. A circular version replaces those boundary conditions with links back into the list. When the list contains several elements, the tail’s next points to the head, while the head’s prev points to the tail.

This arrangement is useful when an operation must continue from the beginning after reaching the end. A Melbourne public transport display, for example, might cycle through route messages, while a game server could rotate through players without restarting a separate traversal. Moving forwards or backwards takes constant time because each node stores both neighbours.

The structure is different from a tree or graph, where traversal generally depends on reaching a terminal node. A circular list has no natural stopping point, so an iterator should stop when it reaches a saved starting node. The same idea appears in graph work: an article about strongly connected components shows why cycles need deliberate visitation rules rather than a simple NULL test.

Representation And Invariants

A sentinel, also called a dummy node, is a convenient permanent node that represents the boundary of the list. It does not contain user data. In an empty list, its next and prev pointers refer to itself. In a non-empty list, sentinel.next is the first data node and sentinel.prev is the last.

The key invariants should remain true after every public operation:

• An empty list has sentinel.next == &sentinel and sentinel.prev == &sentinel.
• Every node’s next->prev and prev->next point back to that node.
• The first data node follows the sentinel, and the last data node precedes it.
• The stored size equals the number of allocated data nodes.

A compact type definition can represent this design:

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct {
    Node sentinel;
    size_t size;
} CircularList;

The sentinel lives inside CircularList, so it must never be passed to free. This is one reason a separate size field is useful: it gives callers an immediate length and helps diagnostic code detect accidental corruption.

Building Core Operations

Initialisation must make the sentinel self-referential. Insertion then becomes a general operation that places a new node between two existing nodes. The same helper can support insertion at the front and back, avoiding separate pointer logic for empty and non-empty cases.

static void list_init(CircularList *list)
{
    list->sentinel.next = &list->sentinel;
    list->sentinel.prev = &list->sentinel;
    list->size = 0;
}

static Node *node_create(int value)
{
    Node *node = malloc(sizeof *node);

    if (node != NULL) {
        node->value = value;
        node->prev = NULL;
        node->next = NULL;
    }
    return node;
}

static void insert_between(CircularList *list,
                           Node *left, Node *right, int value)
{
    Node *node = node_create(value);

    if (node == NULL) {
        return; /* A production API should report this failure. */
    }

    node->prev = left;
    node->next = right;
    left->next = node;
    right->prev = node;
    list->size++;
}

void list_push_front(CircularList *list, int value)
{
    insert_between(list, &list->sentinel,
                   list->sentinel.next, value);
}

void list_push_back(CircularList *list, int value)
{
    insert_between(list, list->sentinel.prev,
                   &list->sentinel, value);
}

Removing a node is the reverse operation. First reconnect its neighbours, then release its memory. The sentinel must be protected because unlinking and freeing it would invalidate the whole container.

bool list_remove(CircularList *list, Node *node)
{
    if (node == NULL || node == &list->sentinel) {
        return false;
    }

    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
    list->size--;
    return true;
}

A traversal can begin at sentinel.next and continue until it reaches the sentinel again. Forward and reverse traversal use the same stopping rule, changing only the selected link. Store the initial node if traversal may modify the list during iteration; otherwise, deleting the current node can make the next step unsafe.

Handling Ownership And Errors

Every successful call to node_create transfers ownership of the returned node to the list. The list therefore becomes responsible for freeing each node during removal or destruction. Returning void from list_push_front hides allocation failure, so a stronger interface should return bool or an error code.

bool list_push_back_checked(CircularList *list, int value)
{
    Node *node = node_create(value);

    if (node == NULL) {
        return false;
    }

    node->prev = list->sentinel.prev;
    node->next = &list->sentinel;
    list->sentinel.prev->next = node;
    list->sentinel.prev = node;
    list->size++;
    return true;
}

void list_clear(CircularList *list)
{
    Node *current = list->sentinel.next;

    while (current != &list->sentinel) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    list_init(list);
}

The checked insertion function illustrates an important C practice: allocate before changing any links. If malloc fails, the original list remains intact. For a larger implementation, document whether functions accept only valid list pointers, whether nodes may belong to another list, and whether stored values are copied or owned through pointers.

The broader C programming material is useful for reviewing pointer lifetimes, structures, allocation, and undefined behaviour. Compile with warnings enabled, such as -Wall -Wextra -Wpedantic, and use sanitiser builds when available. AddressSanitizer can expose use-after-free errors, while UndefinedBehaviorSanitizer can reveal invalid operations that ordinary tests miss.

If node values represent customer identifiers, contact details, or usage records, the data model also deserves attention. An Australian organisation covered by the Privacy Act 1988 may need to consider the Australian Privacy Principles when handling personal information. A linked list does not provide deletion guarantees by itself: removing a pointer frees storage, but backups, logs, or copied strings may require separate retention controls.

Complexity Testing And Practical Use

Insertion at either end is O(1) when the sentinel and size field are maintained. Removing a node is also O(1) when the caller already has its address. Searching for a value takes O(n), and traversing all nodes takes O(n). The extra space is O(n) for the allocated nodes, with constant container overhead.

A small validation function can check the structural invariants after each operation. It should count nodes in both directions, verify reciprocal links, and stop after at most size steps. A hard limit is important: if a pointer is corrupted and the sentinel can no longer be reached, an unchecked diagnostic loop may itself run forever.

Useful tests should include:

• Initialising, clearing, and destroying an empty list.
• Inserting one item at the front and back, then checking both directions.
• Removing the first, last, and only data node.
• Traversing forward and backward after mixed insertions and deletions.
• Simulating allocation failure and confirming that existing links remain valid.

A circular list can model a rotating work queue in a Sydney technology service, a playlist used during a Brisbane event, or a round-robin process table in a Perth mining application. In production code, the choice should reflect the access pattern: arrays usually offer better cache locality for indexed data, while linked nodes are helpful when stable node addresses and frequent local insertions matter.

Performance testing should use realistic workloads rather than assuming pointer operations are always faster. Repeated heap allocation can be costly, and scattered nodes may cause cache misses. If the Australian software market requires predictable latency, a node pool or arena allocator may reduce allocation overhead, though that introduces pool lifetime and capacity concerns. The final implementation should be measured, tested, and documented around its ownership rules rather than selected solely because its asymptotic complexity looks attractive.