Linked list
A chain you can splice.
Built into the IPL language for symbolic AI research. The trio wanted to manipulate structures of structures (symbol manipulation, theorem proving), and arrays were too rigid. The cons cell of LISP descends directly from this work two years later.
Each node holds a payload and a pointer to the next. Insert/delete at a known position is O(1): just rewire pointers. Random access is O(n) because there is no arithmetic shortcut.
Linux kernel's list_head. Java's LinkedList. Functional languages' "cons" lists. Most concurrent queues. The free list inside any allocator.
Almost always slower than an array in practice. Pointer chases miss cache. Useful when (a) you need O(1) splicing, (b) you don't know capacity, or (c) the language gives you no choice.