What is a linked list?

A linked list stores a sequence of values as a chain of separate elements, with each element holding both its own value and a reference pointing to the next element in the chain, trading away an array‘s instant access by position in exchange for the ability to grow, shrink, and rearrange the sequence flexibly without needing to move everything else around.

How does a linked list’s structure actually differ from an array’s, given that both store a sequence of values?

An array, covered elsewhere in this glossary, stores its values contiguously in memory, letting any element be reached instantly by calculating its position directly. A linked list instead scatters its elements freely across memory, connecting them only through explicit references from one element to the next, which means reaching a specific element requires walking through the chain from the beginning rather than jumping straight to it. What a linked list gains in exchange for losing this instant access is flexibility: inserting or removing an element in the middle of a linked list only requires updating a couple of references, without needing to shift every subsequent element over the way an array insertion or removal typically would.

Where does this kind of flexible, reference-based structure actually show up inside HNSW’s own design?

HNSW‘s neighbor lists, the connections each vector maintains to nearby vectors at each layer of the graph, need to grow, shrink, and get reorganized frequently as vectors are inserted and as the neighbor-selection heuristic, covered elsewhere on this site, prunes and replaces connections over time. While many practical implementations favor array-like storage for these neighbor lists specifically for the performance reasons covered in this site’s page on how HNSW‘s data structures should be laid out in memory, the underlying conceptual need being served, a flexible collection whose size and contents shift over time, is exactly the problem a linked list is built to solve, and some implementations do use linked-list-style structures for exactly this reason where flexibility matters more than the memory-layout benefits an array provides.

Why might a real implementation ultimately choose array-like storage over a genuine linked list even for a naturally variable-sized collection like a neighbor list?

A linked list’s scattered memory layout works against a computer’s memory caching behavior, which strongly favors accessing memory locations that sit near each other in sequence rather than jumping between distant, unpredictable locations, covered in more depth in this site’s coverage of memory layout for performance. Because HNSW’s search process repeatedly reads through the same neighbor lists over and over as it navigates the graph, this caching penalty tends to outweigh a genuine linked list’s flexibility advantage in practice, which is exactly why real-world HNSW implementations often favor array-like structures for neighbor lists despite their variable size, accepting somewhat more complex resizing logic in exchange for the faster, more cache-friendly access an array-like layout provides.

Understanding a linked list’s flexible but scattered structure, in direct contrast to an array’s contiguous but fixed-size layout, clarifies exactly why HNSW’s real implementations tend to favor array-like storage even for collections that naturally change size over time. From here, the pages on array and on how HNSW’s data structures should be laid out in memory for performance dig further into this trade-off in more concrete implementation terms.