Linked Lists, Stacks & Queues: Implementation Notes

01The abstraction boundary

A stack or queue specifies observable behavior; an array or linked list specifies a representation. Keeping these layers separate lets an implementation change without changing its public interface.

02What a pointer path really means

struct Node {
    int data;
    struct Node *next;
};

The familiar picture 10 → 20 → 30 describes logical order. Each node is normally a separate heap allocation, so its successor can be far away in the process's address space.

03The same program on 32-bit and 64-bit machines

Consider the same definition on both targets:

struct Node {
    int data;
    struct Node *next;
};

The list algorithm is unchanged: next still identifies the successor and NULL still terminates the list. What changes is the binary representation. The comparison below reflects common ILP32 and LP64/LLP64 ABIs; it is typical, not a language guarantee.

Measure the actual ABI

#include <stddef.h>
#include <stdio.h>

struct Node {
    int data;
    struct Node *next;
};

int main(void) {
    printf("pointer size : %zu\n", sizeof(void *));
    printf("node size    : %zu\n", sizeof(struct Node));
    printf("next offset  : %zu\n", offsetof(struct Node, next));
    printf("node align   : %zu\n", _Alignof(struct Node));
    return 0;
}

When supported by the toolchain, compile the test separately with -m32 and -m64. A 64-bit operating system may run a 32-bit binary through a compatibility subsystem; a 32-bit operating system cannot run a 64-bit binary. The same source is portable only after recompilation for the target architecture.

pointer size : 4
node size    : 8
next offset  : 4
node align   : 4

pointer size : 8
node size    : 16
next offset  : 8
node align   : 8

Consequences beyond node size

• Cache density: ignoring allocator overhead, a 64-byte cache line could hold eight 8-byte nodes but only four 16-byte nodes if the nodes were contiguous.
• Address printing: use printf("%p", (void *)pointer). Converting a pointer to int truncates it on common 64-bit targets.
• Structure layout: compiler options such as packing can change offsets, but packed pointers may be misaligned and slower or invalid on some architectures.
• Data models: 64-bit Unix-like systems commonly use LP64, while 64-bit Windows uses LLP64. Pointer width is 8 bytes in both, but the size of long differs.

04Memory-system costs

The source-level node is not the allocation size

On a common 64-bit ABI, an int uses 4 bytes and a pointer 8 bytes. Alignment can add 4 bytes of padding, producing a 16-byte C structure. This is only the object layout—not necessarily the complete allocator cost.

General-purpose allocators round requests to size classes and maintain metadata, often beside the object or in separate bookkeeping structures. One million integers therefore need about 4 MB in a packed C array, at least 16 MB as these nodes, and potentially more after size-class rounding and fragmentation. Exact totals must be measured for the allocator and platform in use.

Why pointer chasing stalls a modern CPU

05Reading complexity claims correctly

A complexity statement is meaningful only with its preconditions and cost model. “Linked-list insertion is O(1)” describes pointer rewiring after the relevant node is available; it does not promise that locating or allocating that node is free.

06Choosing a representation

Allocation strategy can change the result

A node pool, slab, or arena allocates nodes in batches. This can reduce per-node metadata, improve locality, make allocation more predictable, and limit fragmentation. It also changes reclamation: an arena commonly frees many objects together rather than individually.

07Implementation details for stacks and queues

Array stacks: fast paths and latency spikes

Most pushes perform one bounds check and one write. A growth push allocates a larger buffer, moves or copies the live elements, and invalidates addresses into the old buffer. Amortized O(1) explains total work over a sequence; it does not guarantee constant latency for an individual push. Systems with strict latency targets may reserve capacity in advance or use fixed-capacity storage.

Circular queues: the invariant is the design

Power-of-two capacities permit index & (capacity − 1) instead of modulo, but only when that power-of-two invariant is guaranteed. In concurrent queues, head/tail updates also require a defined atomic-memory-ordering protocol; volatile variables alone are not sufficient.

08Lifetime, ownership, and executable invariants

Relinking removes a node from the logical structure; it does not, by itself, end the payload's lifetime or release storage. A correct manual-memory implementation needs a clear owner and a defined order: preserve required links, unlink, destroy the payload, release the allocation, and invalidate obsolete references.

These are not merely documentation. In debug builds they can become assertions checked after every mutation; property-based tests can generate operation sequences and verify that the invariants always survive.

Node *p = malloc(...);
p = NULL;

free(p);
printf("%d", p->data);

head = head->next;
/* old head not freed */

09Choosing and measuring a representation

Modern CPUs usually reward contiguous storage. Dynamic arrays can outperform linked lists even when occasional shifts occur because they reduce allocations and pointer overhead while enabling prefetching and vectorization. A linked representation remains valuable when stable node addresses, constant-time splicing at known positions, or non-moving objects are actual requirements.

Benchmark the representation, not a toy operation

Review checklist

1. Which precondition makes the quoted operation bound true?
2. How many useful payload bytes fit in each fetched cache line?
3. Will growth or mutation invalidate stored references?
4. Who owns each allocation, and when is it reclaimed?
5. Which invariants make empty and full states unambiguous?
6. Does the benchmark include the costs the application will actually pay?