C Linked Lists: Singly, Doubly & Circular — A Complete Implementation Guide

C Linked Lists: Singly, Doubly & Circular — A Complete Implementation Guide

Table of Contents

• Why Linked Lists? Arrays vs Linked Lists
• The Anatomy of a Linked List Node
• Singly Linked List: Full Implementation
• Doubly Linked List: Two-Way Traversal
• Circular Linked List: Round-Robin Scheduling
• Memory Management: Freeing the Entire List
• The LRU Cache Pattern
• Intrusive Linked Lists: The Linux Kernel Approach
• Performance Analysis: Cache Misses and Fragmentation
• Frequently Asked Questions
• Key Takeaway

Why Linked Lists?

To choose the right data structure, you must understand the trade-offs at the memory level:

Use a linked list when: You need frequent insertions/deletions at arbitrary positions, memory fragmentation is not a concern, and sequential traversal is acceptable.

Use an array when: You need random access by index, cache performance is critical, or the dataset is mostly read and rarely modified.

The Anatomy of a Linked List Node

Each node in a linked list is a self-referential struct: it holds data and a pointer to the next node of the same type:

The key insight: struct Node *next is a pointer to the same struct type. This self-reference is what creates the chain. Each node can be anywhere in heap memory — they do not need to be contiguous.

Singly Linked List: Full Implementation

A complete, production-quality singly linked list with all fundamental operations:

Doubly Linked List: Two-Way Traversal

Adding a prev pointer enables O(1) backward traversal and more efficient deletion (no need to track the previous node separately):

Circular Linked List: Round-Robin Scheduling

In a circular linked list, the last node's next pointer points back to the head. This creates an endless cycle — perfect for round-robin scheduling and game loops:

Memory Management: Freeing the Entire List

The most critical rule: every node was individually malloc'd, so every node must be individually free'd:

The most common mistake is using current->next after free(current) — accessing a freed node's data is undefined behavior.

The LRU Cache Pattern

An LRU (Least Recently Used) cache is one of the most common uses of a doubly linked list in production systems. It maintains a list ordered by recency: most recently accessed at the head, least recently accessed at the tail:

Redis, memcached, and virtually every operating system page replacement policy use this exact pattern.

Intrusive Linked Lists: The Linux Kernel Approach

The Linux kernel's list implementation is different from the textbook approach. Instead of a node containing data, the data struct contains the list node. This is the "intrusive" linked list pattern:

Advantages: A single task can be on multiple lists simultaneously (run queue, wait queue, timer list) by embedding multiple list_head members. No extra allocation per node — the node is embedded directly in the data struct.

Performance Analysis: Cache Misses and Fragmentation

The biggest practical disadvantage of linked lists is cache performance. Nodes are allocated individually with malloc, which scatters them throughout the heap:

• Array sequential iteration: CPU prefetcher loads the next 64 bytes (up to 16 ints) into L1 cache automatically.
• Linked list sequential iteration: Each ->next pointer follows an address that may be anywhere in virtual memory — potentially a cache miss on every node.

On modern CPUs, an L1 cache miss costs ~4 cycles; an L2 miss costs ~12 cycles; an L3 miss costs ~40 cycles; a RAM fetch costs ~200 cycles. For large linked lists in performance-critical code, this is a severe bottleneck.

Solutions:

• Memory pool allocator: Pre-allocate a pool of nodes from a single large block. Adjacent nodes are then near each other in memory.
• Indexed linked lists: Use array indices instead of pointers — nodes live in an array, and next is an integer index.
• Slab allocator: Used in the Linux kernel — pre-allocates fixed-size objects in contiguous slabs.

Frequently Asked Questions

Why is insert-at-head O(1) but insert-at-middle O(n)? Inserting at the head requires only updating one pointer (new->next = head; head = new). Inserting at an arbitrary position requires first finding that position, which requires traversing from the head — an O(n) operation. If you already have a pointer to the node, insertion is O(1) (which is why doubly linked lists are preferred — deletion of a known node is O(1) without the traversal).

How does the Linux kernel implement its linked list? The kernel uses struct list_head — a doubly linked circular list embedded as a field inside the data structure (struct task_struct, struct inode, etc.). This intrusive design allows a single kernel object to participate in multiple lists simultaneously and avoids the extra heap allocation of storing a node pointer.

When should I use a hash table instead of a linked list for lookups? Always. For lookup by key, a hash table gives O(1) average vs O(n) for a linked list. Linked lists are primarily valuable for ordered collections that need frequent insertion and deletion. The classic combined structure is a hash table (for O(1) lookup) + doubly linked list (for O(1) ordered operations) — the foundation of LRU caches.

What is the "pointer to pointer" trick in list deletion? Node **current = &list->head is a pointer to the head pointer itself. By working through *current (the pointer it points to), you can uniformly handle deletion of the head node and middle nodes without a special case. When *current = node->next, you're updating whichever pointer (head, or a previous node's next) currently points to the deleted node.

Key Takeaway

Linked lists are the gateway to complex, self-referential data structures. Their power lies not in raw traversal speed (arrays win there) but in their ability to insert and delete O(1) at any known position, dynamically grow without reallocation, and participate in sophisticated patterns like LRU caches and kernel scheduler queues.

In systems programming, you will use linked lists everywhere — from OS process scheduling to interpreter object reference tracking to network buffer queues. Mastering the implementation at the pointer level gives you a tool belt that serves across every large-scale C system.

Read next: Hash Tables & Collision Resolution: O(1) Lookup in C →

Part of the C Mastery Course — 30 modules covering everything from C basics to kernel-level systems engineering.