Linked lists

An array keeps its elements side by side, which makes indexing instant but inserting in the middle slow. A linked list makes the opposite trade. Each element lives in its own small block of memory, called a node, and each node holds a pointer to the next node. The order of the list is carried by the pointers, not by the positions in memory, so a new node can be spliced in anywhere by changing two pointers, without moving any other element. The price is that there is no address arithmetic: to reach the hundredth element you must follow ninety-nine pointers from the start. Linked lists appear throughout systems software, in operating system run queues, memory allocators' free lists, device driver buffer chains and the hash table buckets of lesson 10, and understanding them is a rite of passage in pointer manipulation.

The NS-4 gives Jonah a natural use. Besides vehicle records, the node keeps a list of pending events: a loop sensor that has stopped responding, a door switch that opened, a battery voltage below threshold, a firmware update waiting to be installed. Events arrive at unpredictable times, some are cleared out of order when the condition resolves, and each upload reports whatever is still pending. The list rarely holds more than a dozen events, but they come and go in any order, which is exactly where splicing nodes in and out is useful.

Singly linked lists

In a singly linked list, each node holds a value and one pointer, next, to the following node. The list itself is represented by a pointer to the first node, called the head; the last node's next pointer is null, marking the end. Traversing the list means starting at the head and following next pointers until reaching null. Many implementations also keep a tail pointer to the last node, so that appending at the end is O(1) instead of requiring a walk through the whole list, and a count of the nodes, so that the size is available without counting.

The basic operations show the trade-offs clearly. Inserting at the head is O(1): create a node, point its next at the current head, and make it the new head. Inserting after a node you already hold a pointer to is also O(1): point the new node's next at that node's successor, then point that node's next at the new node. The order of those two assignments matters; doing them the other way round loses the rest of the list. Deleting the node after a given node is O(1): point the given node's next past the doomed node. But finding a node by value or by position is O(n), because there is no way to jump into the middle of the list, and deleting a node when you hold a pointer only to that node is awkward in a singly linked list, because you need its predecessor to repair the chain.

# A singly linked list of NS-4 events, with head and tail pointers
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, nxt=None):
        self.value, self.next = value, nxt

class EventList:
    def __init__(self):
        self.head = self.tail = None
        self.size = 0

    def append(self, value):                 # O(1) with a tail pointer
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def remove(self, value):                 # O(n): search, then splice out
        prev, cur = None, self.head
        while cur is not None and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False
        if prev is None:
            self.head = cur.next
        else:
            prev.next = cur.next
        if cur is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def __iter__(self):
        cur = self.head
        while cur is not None:
            yield cur.value
            cur = cur.next

events = EventList()
for e in ("loop 2 open circuit", "door opened", "battery 11.6 V", "update ready"):
    events.append(e)
events.remove("door opened")
events.remove("update ready")              # removing the tail must move the tail pointer
events.append("loop 2 restored")
print(list(events), "size", events.size, "tail:", events.tail.value)

['loop 2 open circuit', 'battery 11.6 V', 'loop 2 restored'] size 3 tail: loop 2 restored

The remove method shows the classic pattern: walk with two pointers, prev and cur, so that when cur reaches the target, prev is the node whose next must change. It also shows the edge cases that cause most linked-list bugs. Removing the head has no predecessor, so the head pointer itself must change. Removing the tail must move the tail pointer back, or the next append would attach to a node that is no longer in the list. Removing from an empty list must not crash. A good habit is to test every list routine on an empty list, a one-node list, and removals at the head, the middle and the tail.

Sentinel nodes

The special cases for the head can be removed entirely with a sentinel, also called a dummy node: a node that is always present at the front of the list and holds no real value. The real first element is sentinel.next, an empty list is one whose sentinel.next is null, and every real node has a predecessor, so insertion and deletion never need to change the head pointer. The cost is one extra node of memory. Production code such as the Linux kernel's list library goes further, using a circular doubly linked list with a sentinel, in which the last node points back to the sentinel, so there are no null pointers to check at all.

Doubly linked lists

A doubly linked list gives each node two pointers, next and prev. That costs another pointer per node, but it buys two abilities. You can traverse the list backwards, and you can delete a node in O(1) given only a pointer to that node, because the node itself knows its predecessor: set node.prev.next = node.next and node.next.prev = node.prev, and the node is unlinked. This is why doubly linked lists are the standard structure for least-recently-used caches, where any entry may be moved to the front at any moment, and for operating system queues, where a process may be removed from the middle of a run queue when it blocks.

Linked lists on a microcontroller

On a desktop, each node is allocated from the heap with malloc or by the Python runtime. The NS-4 firmware avoids the heap, as lesson 1 explained, so its event list uses a pool: a fixed array of, say, 32 event nodes reserved at start-up. Unused nodes are themselves kept on a singly linked free list threaded through the array. Allocating a node pops one from the free list in O(1); freeing a node pushes it back in O(1). No fragmentation can occur, because every node is the same size, and the worst case is known exactly: when all 32 nodes are in use, a new event is either dropped or replaces the least important one, by a rule decided at design time rather than discovered in the field.

/* Fixed pool of doubly linked event nodes, with a free list (NS-4 firmware) */
#include <stdint.h>
#include <stddef.h>

typedef struct evnode {
    struct evnode *prev, *next;
    uint16_t code;            /* event code      */
    uint32_t time_s;          /* seconds of day  */
} evnode_t;

#define EV_POOL 32
static evnode_t pool[EV_POOL];
static evnode_t *free_list;               /* singly linked through next */
static evnode_t active = { &active, &active, 0, 0 };   /* circular sentinel */

void ev_init(void)
{
    free_list = NULL;
    for (int i = EV_POOL - 1; i >= 0; i--) { pool[i].next = free_list; free_list = &pool[i]; }
}

evnode_t *ev_add(uint16_t code, uint32_t t)        /* O(1); NULL when the pool is empty */
{
    evnode_t *n = free_list;
    if (n == NULL) return NULL;
    free_list = n->next;
    n->code = code; n->time_s = t;
    n->prev = active.prev; n->next = &active;        /* insert before the sentinel: at the tail */
    active.prev->next = n; active.prev = n;
    return n;
}

void ev_clear(evnode_t *n)                          /* O(1) unlink, then return to the pool */
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->next = free_list; n->prev = NULL;
    free_list = n;
}

Note that the sentinel, active, is initialized to point to itself in both directions: an empty circular list. Insertion at the tail places the new node between the current last node, active.prev, and the sentinel. Clearing an event unlinks it and pushes it onto the free list. Every operation is a handful of pointer assignments with no loops, so the worst-case execution time is tiny and constant, which matters because events are often raised from interrupt handlers. Because the main loop and interrupt handlers may touch the list at the same time, the real firmware briefly disables interrupts around ev_add and ev_clear; ignoring that would let an interrupt see a half-updated pair of pointers.

Linked lists versus arrays

On paper the linked list wins any contest that involves inserting or deleting in the middle, and the array wins any contest that involves indexing. In practice, on large modern processors, arrays win far more often than the table of costs suggests. Finding the place to insert in a linked list is itself O(n), and that walk follows pointers through scattered memory, missing the cache at almost every node, while shifting elements in an array is a single fast memory move over contiguous data. Benchmarks routinely show that inserting into the middle of a dynamic array of a few thousand integers beats a linked list, even though both are O(n), because the array's constant factor is far smaller. Linked lists earn their place when you already hold a pointer to the node to remove, when elements are large and must not move because other code points at them, or when nodes come from a fixed pool as on the NS-4.