Linked list vs CSR adjacency

Storing adjacency is a three-way trade among mutability, compactness, and cache-locality: doubly-linked lists chase pointers across the heap but insert and delete cheaply (right for mutating OLTP graphs), while CSR streams a node's neighbors contiguously through cache but must rebuild to add an edge (right for read-mostly analytic sweeps).

Previously

The doubly-linked list mutates cheaply, but it scatters across memory — every hop is a potential cache miss. CSR packs a node's neighbors into one contiguous slice that flies through cache, at the price of never being able to cheaply add an edge. That's the storage fork; now both layouts are just bytes. The thing missing is a way to ASK questions of them without hand-coding pointer walks.

Scene 06

Linked list vs CSR adjacency

Watch
Try it
Predict
Capture

What to watch for

Last scene the relationship chain was a doubly-linked list because it's easy to insert and delete. But pointer-chasing across the heap is cache-hostile. Watch Alice's four friends drawn first as that scattered list — each cell at its own heap address, chained by prev/next — then drawn a second way: packed into one contiguous slice that reads straight through cache. Same four neighbors, two completely different memory layouts.

Alice's four FRIEND neighbors, drawn two ways.
Left — a doubly-linked relationship list: each neighbor is a record sitting at its own scattered heap address, chained by prev/next pointers, so walking the chain jumps all over memory (a cache miss per hop).
Right — CSR (Compressed Sparse Row): one offset array plus one packed neighbor array, where Alice's neighbors are the contiguous slice neighborArray[offset[v]:offset[v+1]] that streams straight through cache.
The 'insert a friend' action shows the fork: the list splices one cell in place, while CSR must rebuild the whole array.
The three-way trade legend reads off mutability vs compactness vs cache-locality.

Implementation

Highlighted lines are the ones running in the diagram right now.

CSR.neighbors

a vertex's neighbors are one contiguous slice — a single cache stream

1def neighbors(v, offset, neighbor_array):
2    start = offset[v]
3    end   = offset[v + 1]
4    # contiguous run — streams through cache
5    return neighbor_array[start:end]

insert_edge

in-place splice on the list vs full rebuild on CSR

1def insert_list(cell, after):       # doubly-linked list
2    cell.next = after.next          # rewire two pointers
3    after.next = cell               # O(1) — splice in place
4 
5def insert_csr(v, u, offset, arr):  # CSR — no free slot
6    arr = rebuild_with_edge(v, u)   # O(total edges) rebuild
7    return arr

List.walk

the read-side cost the left pane draws — each hop follows a pointer to a new heap address

1def walk_list(head):            # doubly-linked relationship chain
2    cell = head
3    while cell is not None:
4        visit(cell.id)             # use this neighbor
5        cell = cell.next           # pointer → some other heap address
6        # next cell is elsewhere → likely a cache miss

Store.pickLayout

match the layout to whether the graph mutates or just gets read

1def pick_layout(workload):
2    if workload.mutates_constantly:
3        return LINKED_LIST   # splice edges in place, skip rebuilds
4    else:                    # read-mostly: never inserts
5        return CSR           # contiguous neighbors stream through cache

Sources

Where this sits in Build a graph database (Neo4j / Dgraph-style)

Scene 06 of 16, in the The store act — Store records, index-free adjacency, the CSR trade.. Doubly-linked relationship lists are cache-hostile but mutate in place; Compressed Sparse Row packs a node's neighbors into one contiguous slice that streams through cache but rebuilds the whole array to add a single edge — the OLTP-graph vs OLAP-graph storage fork.

Up next. We can store and traverse a graph by hand, but nobody writes raw pointer-walks. We need a language where you describe the SHAPE you want — Alice's friends' friends — and the engine compiles it into a traversal. And the surprising part: for expansion, that compiler needs no join planner at all, because the pattern maps straight onto pointer-chasing.

All 16 scenes in Build a graph database (Neo4j / Dgraph-style) · Every curriculum

Built with Arqly

Every scene in Build a graph database (Neo4j / Dgraph-style) builds on the one before it.All 16 Build a graph database (Neo4j / Dgraph-style) scenes