linked list

A sequence made of nodes scattered in memory, each holding a value and a pointer to the next node.

In more detail

Inserting or removing next to a node you already hold costs O(1): you only rewire a pointer. Reaching position k means walking from the head through k nodes, so index access is O(n). Linked lists win when you hold references to nodes and must splice them in and out often, as in timer queues and LRU caches.

Example

React fibers point to child, sibling and parent, and each fiber stores its hooks as a list walked in call order.

Related terms

Taught in

References