Nodes, Pointers & Memory Layout

July 2026 · 18 min read

Before a single algorithm, you need an accurate mental picture of what a linked list is once the compiler is done with it. Almost every wrong intuition about linked lists — "they're faster for insertion", "they save memory", "they avoid copying" — comes from reasoning about the diagram instead of the machine. This post fixes the picture.

What a Node Actually Is

A node is a struct. Nothing more:

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

On a typical 64-bit platform, int is 4 bytes and Node* is 8 bytes. But sizeof(Node) is 16, not 12: the pointer must be 8-byte aligned, so the compiler inserts 4 bytes of padding after val. That is a 33% overhead you did not write and cannot see.

// offsetof(Node, val)  == 0
// offsetof(Node, next) == 8   <- 4 bytes of padding at [4, 8)
// sizeof(Node)         == 16

static_assert(sizeof(Node) == 16);
static_assert(alignof(Node) == 8);

So storing one million ints in a linked list costs 16 MB of node payload, versus 4 MB for a std::vector<int>. And that is before the allocator's own bookkeeping.

The Cost You Do Not See: The Allocator

new Node is not free and it is not just sizeof(Node). A general-purpose allocator like glibc's malloc stores a header immediately before each allocation (typically 8 or 16 bytes recording the chunk size and flags) and rounds the request up to a size-class boundary — usually a multiple of 16 bytes with a 32-byte minimum.

Realistically, a 4-byte integer in a linked list occupies 32 bytes of resident memory — an 8× expansion. This is why "linked lists save memory" is backwards. They save memory only when the payload is large relative to a pointer, or when you would otherwise have to over-allocate an array.

Pointer Chasing vs. Sequential Scanning

Here is the part that decides real benchmarks. Consider summing every element.

// Array: the address of element i is known before the load issues.
long sum = 0;
for (int i = 0; i < n; ++i) sum += a[i];

// List: the address of element i+1 is *inside* element i.
long sum = 0;
for (Node* p = head; p; p = p->next) sum += p->val;

These look equally cheap. They are not, and the reason is dependency, not instruction count.

In the array loop, the CPU computes a + i with arithmetic. It knows the next several addresses long before it needs them, so the hardware prefetcher streams cache lines ahead of the loop and every load hits L1. A 64-byte cache line holds 16 ints, so you pay one memory access per 16 elements.

In the list loop, p->next must complete before the next iteration's address is even known. This is a serial dependency chain of loads: the prefetcher cannot help, out-of-order execution cannot help, and if the node is not cached you stall for the full latency of the memory hierarchy on every single element.

The practical numbers, on a modern desktop CPU:

An array sum runs at roughly one element per cycle. A scattered linked-list sum can run at one element per 200 cycles. That is the two-orders-of-magnitude gap people find shocking, and it does not show up in Big-O at all — both are O(n).

The Locality Illusion

Freshly-built lists benchmark deceptively well. If you allocate a million nodes in a tight loop on a fresh heap, the allocator hands back nearly-contiguous chunks, so traversal order roughly matches address order and the prefetcher partially rescues you.

// Benchmarks great: nodes come out of the allocator in address order.
for (int i = 0; i < n; ++i) push_front(i);

// Benchmarks terribly: the same nodes, visited in a shuffled order,
// after a workload that has fragmented the heap.

Real workloads insert, delete, and interleave allocations from other subsystems. After a few hours, the traversal order of a long-lived list has essentially no relationship to its address order, and every hop is a potential TLB and cache miss. Benchmark lists after fragmentation, not before.

The Ownership Question

Every list implementation must answer one question before it writes a single method: who frees the nodes? There are exactly three answers, and mixing them is where memory bugs come from.

1. The list owns nodes via raw pointers

The classic teaching design. The list allocates in push, frees in pop, and frees everything in the destructor. Simple, fast, and entirely on you to get right — you must also delete the copy constructor and copy assignment, or a copy will double-free.

class List {
    Node* head_ = nullptr;
public:
    List() = default;
    List(const List&)            = delete;   // or implement a deep copy
    List& operator=(const List&) = delete;

    ~List() {
        while (head_) { Node* nx = head_->next; delete head_; head_ = nx; }
    }
};

2. The list owns nodes via unique_ptr

Correct by construction, and free of leaks. The cost is that unlinking becomes a dance of std::move, and the destructor is still recursive — destroying the head destroys its unique_ptr<Node> next, which destroys the next, and so on. You must break the chain manually.

struct Node {
    int val;
    std::unique_ptr<Node> next;
};

// Still required: an iterative teardown, or deep lists overflow the stack.
~List() {
    while (head) head = std::move(head->next);
}

3. Something else owns the nodes (intrusive)

The list stores no allocations at all: the next pointer lives inside the user's object, and the list is just a chain through objects that already exist. Zero allocation, zero indirection to the payload, and the pattern the Linux kernel uses everywhere. Covered in Unrolled & Intrusive Lists.

struct ListHead { ListHead *next, *prev; };

struct Task {
    int  pid;
    ListHead run_queue;   // the list threads through the object
};

Representing "End of List"

Three conventions exist, and they change every loop condition you will write:

The standard library uses the sentinel convention: std::list keeps one non-allocating end node so that end() is a real, dereferenceable-adjacent iterator and --end() gives you the last element.

When Lists Genuinely Win

Given everything above, a linked list is still the right structure when:

• References must stay valid. Pushing into a std::vector can reallocate and invalidate every pointer, reference, and iterator into it. Pushing into a std::list invalidates nothing. This alone justifies most production uses.
• You splice instead of copy. Moving a range of 10 million elements from one std::list to another is O(1) — four pointer writes. No allocation, no moves, no invalidation. There is no array equivalent.
• You already stand at the node. An LRU cache holds a pointer to the node it needs to move; the move is O(1). Finding position i would be O(n), but it never has to.
• Latency spikes are unacceptable. A vector's amortized O(1) push is O(n) on the resize. Real-time and audio code cannot take that one long frame.
• Elements are huge or non-movable. When copying an element costs more than chasing a pointer, the arithmetic flips.
• The node is already allocated by someone else. Intrusive lists cost literally nothing to join.

Notice what is missing from that list: "insertion is O(1)". Insertion into a linked list at a position you must first find is O(n) — the same as an array, but with worse constants. The O(1) applies only once you already hold the node.

Check Yourself

Answer before you continue. You are given the situation; pick the correct conclusion.

Practice

• Write the struct Node above and print sizeof(Node) for payloads of char, int, double, and std::string. padding explain each result.
• Build a 10-million-node list and a 10-million-element vector, sum both, and time them. locality then shuffle the list nodes in memory and re-time.
• LeetCode 707 — Design Linked List ownership implement it with raw pointers and again with unique_ptr.
• Take a list of 1,000,000 nodes and destroy it with a recursive destructor. stack observe the crash, then fix it iteratively.