Linked Lists

Part of Programming Fundamentals

A linked list stores elements as individually allocated nodes connected by pointers, enabling dynamic size changes and efficient insertion without pre-allocated contiguous memory.

Why This Matters

Arrays require you to know the maximum size of your data in advance and allocate all that memory upfront, even if you use only a fraction. For data that grows and shrinks unpredictably — a queue of messages, a list of active alarms, a table of registered users — this inflexibility is a real constraint.

Linked lists solve this by allocating memory one element at a time, with each element pointing to the next. The list grows as elements are added and shrinks as they are removed, using only as much memory as currently needed. Insertions and deletions at any point are O(1) operations once you have a pointer to the right location — no shifting of elements required.

For a rebuilding civilization’s early software infrastructure, linked lists appear constantly: the symbol table in an assembler is a linked list. The line store in a BASIC interpreter is a linked list. The free memory list in an allocator is a linked list. The process list in a simple operating system is a linked list. Understanding how they work and when to use them is fundamental to building these systems.

Structure of a Node

A linked list node contains a payload (the data you care about) and a pointer (the address of the next node). In memory, each node occupies a fixed number of bytes.

For a simple integer list:

; Node layout (4 bytes per node):
; Offset 0-1: value (16-bit integer)
; Offset 2-3: next pointer (16-bit memory address, or 0 if last node)

NODE_VALUE  EQU 0    ; offset to value field
NODE_NEXT   EQU 2    ; offset to next pointer field
NODE_SIZE   EQU 4    ; total bytes per node

The list is accessed through a HEAD pointer — the address of the first node. An empty list has HEAD = 0 (null). The last node has its next pointer = 0.

For a list that also needs to be traversed backward, add a PREV pointer to each node. This doubly linked list costs more memory per node but enables O(1) deletion without knowing the predecessor.

Traversal

To visit every element in the list, follow the chain of next pointers:

; traverse list starting at HEAD, call PROCESS for each node
; HL = HEAD initially
TRAVERSE:
    LD A, H             ; check if pointer is null (HL = 0)
    OR L
    JP Z, DONE          ; exit if null
    CALL PROCESS        ; process node at HL (value at offset 0)
    LD A, (HL + NODE_NEXT)     ; load next pointer low byte
    LD H, (HL + NODE_NEXT + 1) ; load next pointer high byte
    LD L, A
    JP TRAVERSE
DONE:

In higher-level pseudocode:

current = HEAD
WHILE current != 0
    process(current)
    current = current->next
END WHILE

Traversal is O(N) — you must follow the chain all the way from HEAD. This is the main disadvantage compared to arrays. Random access to the Nth element requires traversing N-1 nodes to find it.

Insertion

Insert at head (most common, O(1)):

; Insert new node at address NEW before current head
; NEW->next = HEAD
; HEAD = NEW
LD (NEW + NODE_NEXT), HL    ; new->next = old head
LD HL, NEW                  ; head = new node

Insert after a known node (O(1), given pointer to predecessor):

; Insert NEW after node at PREV
; NEW->next = PREV->next
; PREV->next = NEW
LD HL, (PREV + NODE_NEXT)   ; HL = PREV->next
LD (NEW + NODE_NEXT), HL    ; NEW->next = PREV->next
LD HL, NEW
LD (PREV + NODE_NEXT), HL   ; PREV->next = NEW

Insert in sorted position (O(N) — must find the right position by traversal first):

Walk the list until you find the node after which the new element belongs, then insert after it as above.

Deletion

Delete at head (O(1)):

; HEAD = HEAD->next
LD HL, (HEAD + NODE_NEXT)   ; HL = HEAD->next
LD HEAD, HL                 ; HEAD = next
; old head node is now free to reclaim

Delete a known node (requires pointer to predecessor — O(1) if you have it, O(N) to find it):

; PREV->next = NODE->next
LD HL, (NODE + NODE_NEXT)   ; HL = NODE->next
LD (PREV + NODE_NEXT), HL   ; PREV->next = NODE->next
; NODE is now disconnected; free it

This is a key advantage of doubly linked lists: each node contains a prev pointer, so deletion does not require the predecessor. The O(1) deletion property is especially valuable in operating system lists (process lists, I/O queues) where elements must be removed efficiently.

Memory Allocation for Nodes

Where do the bytes for a new node come from? You need a memory allocator.

The simplest allocator for constrained systems is a free list: a linked list of freed node blocks available for reuse. At startup, the allocator divides the available memory pool into fixed-size blocks (all sized for the largest node type) and chains them together as the initial free list.

ALLOC():
    if FREE_LIST == 0: error (out of memory)
    node = FREE_LIST
    FREE_LIST = FREE_LIST->next
    return node

FREE(node):
    node->next = FREE_LIST
    FREE_LIST = node

This allocator runs in O(1) for both allocation and deallocation, with no fragmentation (since all blocks are the same size). It is the right choice for a system that primarily manages same-sized nodes.

For variable-size allocations, a more sophisticated allocator is needed (bump allocator, buddy system, or first-fit free list with coalescing), but fixed-size allocators cover most linked list use cases.

Variations

Circular linked list: The last node’s next pointer points back to the head instead of being null. Useful for round-robin scheduling and ring buffers where you want continuous cycling through elements.

Doubly linked list: Each node has both a next and prev pointer. Enables O(1) deletion without traversal to find the predecessor. Essential for lists where elements are frequently removed from arbitrary positions (process ready queues, LRU caches).

XOR linked list: Stores prev XOR next in a single pointer field instead of two separate fields. Halves the per-node overhead at the cost of slightly more complex traversal code. Useful when memory is extremely scarce. Traverse by keeping track of the previous node’s address and XORing it with the stored value to recover the next node’s address.

Sentinel/dummy head node: Allocate a permanent dummy node as the list head, even for an empty list. Simplifies insertion and deletion code by eliminating special cases for the head node. The sentinel never holds real data; it just holds the first real node’s address.

Linked Lists vs. Arrays: When to Choose

Use an array when:

• Size is known in advance
• Random access by index is needed
• Cache performance matters (arrays are cache-friendly; linked lists are not)
• Simplicity is paramount

Use a linked list when:

• Size changes dynamically and cannot be bounded
• Frequent insertions/deletions in the middle
• Multiple lists share the same nodes (a node can only be in one array position but can be in different lists by changing which pointer chains include it)
• Order changes frequently (reordering is O(1) pointer manipulation, not O(N) element shifting)

Practical Notes for Rebuilders

Implement the ALLOC/FREE free-list allocator before implementing any linked list. Without reliable allocation, linked list code is impossible to test. The allocator is only 10-15 lines of code.

Draw the pointer diagrams before writing insertion and deletion code. For each operation, draw the before state (boxes representing nodes with arrows for pointers) and the after state. Then write code that produces exactly those pointer changes. Pointer manipulation bugs are notoriously subtle and almost always result from incorrect mental models.

In embedded systems code, be extremely cautious about multi-threaded or interrupt-context access to linked lists. The pointer update for insertion or deletion requires multiple steps; an interrupt that accesses the list between those steps can see an inconsistent state. Protect list operations with interrupt disable/enable around the pointer updates.