Linked Lists: Singly, Doubly, Circular

This chapter implements singly linked lists, doubly linked lists, and circular lists, with intrusive and container variants.

Why This Matters

Linked lists are the canonical pointer-based structure. They teach pointer discipline, node ownership, and the trade-offs between contiguous and linked storage. Doubly and circular variants are the backbone of many real systems (LRU caches, schedulers, allocators).

Prerequisites

• c.ds.1 — foundations.
• c.ptr.ptr-to-ptr — pointer-to-pointer (useful for clean insertion).

Core Concept

Singly linked list

Each node has a value and a next pointer:

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

Operations: prepend (O(1)), append (O(1) with a tail pointer, else O(n)), search (O(n)), delete (O(n) to find predecessor, or O(1) with a pointer-to-pointer).

Doubly linked list

Each node has next and prev:

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

Enables O(1) deletion at a known node and backward traversal.

Circular list

The last node's next points back to the head (singly circular) or both ends link (doubly circular). Useful for round-robin scheduling and ring structures.

Examples

Singly linked list (intrusive)

#include <stdlib.h>

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

Node *node_new(int value)
{
    Node *n = malloc(sizeof *n);
    if (n) { n->value = value; n->next = NULL; }
    return n;
}

void list_push_front(Node **head, int value)
{
    Node *n = node_new(value);
    if (n) { n->next = *head; *head = n; }
}

void list_free(Node *head)
{
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

Doubly linked list deletion

void dlist_remove(Node **head, Node *n)
{
    if (n->prev) n->prev->next = n->next;
    else         *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

How It Works

Each node is a separately allocated object; the list is a chain of pointers. Insertion/deletion rewire pointers without shifting elements, unlike arrays. The cost is O(n) search and poor cache locality (pointer chasing).

Variations

Intrusive lists

The link fields live inside your own struct (e.g., a task control block), so the list does not allocate nodes separately. This is the kernel/embedded idiom.

Sentinel nodes

A dummy head/tail node simplifies edge cases (no NULL checks) at the cost of one extra node.

Common Mistakes

• Forgetting to update both next and prev in doubly lists.
• Losing the head pointer during insertion.
• Not freeing nodes (leaks).
• Dangling pointers after deletion.

Undefined Behavior

• Dereferencing a freed node. VERIFIED
• Dereferencing NULL (e.g., traversing past the end). VERIFIED

Portability

• Plain C; fully portable.

Under the Hood

Each node is a separate heap allocation; traversal follows pointers, causing cache misses (c.perf.2). Intrusive lists avoid per-node allocation overhead.

Practical Usage

• Use singly linked lists for simple stacks/queues and low-overhead insertion.
• Use doubly linked lists when you need O(1) deletion at a known node.
• Use intrusive lists in kernels/embedded where allocation is costly.

Exercises

1. Implement push_front, push_back, find, and remove for a singly linked list. 2. Implement a doubly linked list with insert and remove. 3. Build a circular list and traverse it exactly once. 4. Convert the singly list to an intrusive design.

Deep Challenge

Implement an intrusive doubly linked list (with macros for container_of-style access) and use it to build an LRU cache. Explain the ownership and why intrusive is preferable here.

Related Concepts

• c.ds.2 — dynamic arrays (contrast).
• c.ptr.ptr-to-ptr — pointer-to-pointer.
• c.mem.ownership — node ownership.

References

• Standard data-structure literature; Linux kernel list.h for intrusive style.

Verification

• Linked-list complexity and semantics are standard CS. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Singly linked list
• [ ] Doubly linked list
• [ ] Circular list
• [ ] Intrusive vs. container

Mastery levels