What a data structure actually is
A data structure is an agreement about how values are arranged in memory and what operations are cheap as a result. The values don't change — six numbers are six numbers — but the arrangement decides whether "find the 5th item" or "add to the front" costs one step or a thousand.
Every choice is a trade. Lay items out in one contiguous block and you get instant lookup by position but slow inserts. Link them with pointers and inserts get cheap but lookup-by-position gets slow. The rest of this page lets you feel those trade-offs by running the operations yourself.
Array
Values packed side by side in one continuous block. Each slot has an index, so the computer reaches any element by simple arithmetic — instantly. The catch: inserting at the front means physically shifting everything else over.
Linked list
Each value lives in its own node that also holds a pointer to the next one. Nothing is contiguous, so adding to the front is just re-aiming one pointer — cheap. But to reach the 5th node you must walk from the head, one hop at a time.
Stack — last in, first out
A stack only lets you touch the top. You push a value on and pop the most recent one off — like a pile of plates. This is exactly how a program tracks nested function calls and "undo" history.
Queue — first in, first out
A queue is fair: items leave in the order they arrived. You enqueue at the rear and dequeue from the front — a checkout line. Used anywhere work waits its turn: print jobs, task schedulers, message buffers.
Hash table
Instead of searching, a hash table computes where a value should live. A hash function turns your key into a bucket number, so lookups are near-instant. Type a key — watch it get hashed and dropped into a bucket. Two keys landing in the same bucket is a collision; we just chain them.
Binary search tree
Every node has up to two children, and the rule never breaks: smaller values go left, larger go right. That ordering lets search discard half the remaining tree at each step — the same idea as finding a word in a dictionary without reading every page.
Choosing the right one
There's no "best" structure — only the right fit for the operations you do most. Average-case costs below; the right structure turns a slow column green.
| Structure | Access by position | Search by value | Insert | Delete | Best for |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | fixed lists, fast indexing |
| Linked list | O(n) | O(n) | O(1) | O(1) | frequent front edits |
| Stack | — | O(n) | O(1) | O(1) | undo, call tracking |
| Queue | — | O(n) | O(1) | O(1) | scheduling, buffering |
| Hash table | — | O(1) | O(1) | O(1) | lookups by key |
| Binary search tree | — | O(log n) | O(log n) | O(log n) | sorted, range queries |
Layout is a trade
Contiguous memory buys fast indexing; pointers buy fast edits. You rarely get both at once.
Order the work, not the data
Pick the structure by which operation you run thousands of times, not by what looks neat.
Big-O is about growth
It ignores small inputs. O(1) vs O(n) only matters once n gets large.