Search tools and guides ⌘K
I · The linear primitives

Array

A row of equal-sized boxes.

1957 · John Backus & the FORTRAN team
The story

The first thing FORTRAN gave the world. Backus's team needed a way to address a "table" mathematically, by index, in constant time. Every modern memory system since has been shaped by that one decision: contiguous, fixed-stride, addressable by arithmetic.

How it works

Allocate n × sizeof(T) bytes. Element i lives at base + i × sizeof(T). The CPU can prefetch the next cache line because access is predictable.

Where it lives

Every language. Every database row. Every image, audio buffer, GPU texture, network packet.

The key insight

Cache-friendliness beats algorithmic complexity for n < ~10,000. Linear scan of an array often beats a binary search of a tree because the former never misses cache.

More in The linear primitives
Dynamic array (vector) An array that grows itself. Linked list A chain you can splice. Stack Last in, first out. Queue First in, first out. Deque Both ends, equally. Ring buffer A fixed-size queue that never allocates.
Across the cabinet
II Binary search tree Sorted, but with shortcuts. II AVL tree Always height-balanced, to within one. II Red-black tree Almost balanced, much faster to maintain. II B-tree / B+ tree The shape of a database index. II Heap (binary heap) A priority queue you can grep. II Skip list Probabilistic balance, beautifully. II Trie (prefix tree) A tree you walk one character at a time. II Segment tree Range queries in logarithmic time.
← All data structures