Core Data Structures: Arrays, Hash Tables, Trees & Graphs

Core Data Structures

A data structure is a way of organizing data so the operations you care about are fast. Choosing the right one is one of the highest-leverage decisions in programming: the same algorithm can be trivial or impossibly slow depending on whether lookups are O(1) or O(n). Most real-world performance wins come not from clever code but from picking a structure whose strengths match your access patterns.

The catalog is small and worth knowing cold — arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs. Each makes some operations cheap and others expensive, and understanding those tradeoffs (alongside Big-O) is the foundation everything else builds on.

TL;DR

A data structure trades off the cost of different operations (insert, lookup, delete, order).
Hash tables give O(1) average lookup; arrays give O(1) indexing.
Trees/heaps keep data ordered; graphs model relationships.
Pick the structure whose fast operations match your access pattern.

Quick Example

The same task — "have I seen this before?" — is O(n) in a list but O(1) in a set/hash:

The Core Structures

Arrays & Linked Lists

Arrays store elements contiguously, so indexing is O(1) and they're cache-friendly — but inserting/deleting in the middle shifts everything (O(n)). Linked lists store nodes with pointers, so splicing at a known position is O(1), but you lose random access (finding the nth element is O(n)). Most languages' "list" types are dynamic arrays; reach for a linked list specifically when you insert/remove at ends or splice frequently. See Linked Lists.

Hash Tables

The workhorse of practical programming: a hash table maps keys to values with O(1) average insert, lookup, and delete by hashing the key to a bucket. It's behind dictionaries, sets, caches, and deduplication. The caveats: no inherent ordering, and worst-case O(n) under bad hashing or collisions.

Trees, Heaps & Graphs

Trees keep data ordered — a balanced binary search tree gives O(log n) insert/lookup/delete and supports range queries. See Trees.
Heaps efficiently track the min or max — O(1) to peek, O(log n) to insert/extract — making them the basis of priority queues and "top-k" problems.
Graphs model entities and relationships (nodes + edges) — social networks, dependencies, maps — and are traversed with BFS/DFS. See Graph Algorithms.

Best Practices

Match the structure to the operation you do most — frequent lookups → hash table; ordered/range queries → tree; FIFO/LIFO → queue/stack.
Default to your language's built-ins (dynamic array, hash map, set) — they're well-optimized.
Think in Big-O — know the cost of the operations on your hot path.
Mind constants and cache — arrays often beat linked lists in practice despite equal Big-O.
Use a heap for "top-k" instead of sorting everything.

Common Mistakes

Linear search where a hash would do

Using a list as a queue

FAQ

How do I choose the right data structure?

Identify the operations you perform most on the hot path — lookups, insertions, ordered iteration, min/max, range queries — and pick the structure that makes those O(1) or O(log n). Frequent key lookups favor a hash table; ordered data and ranges favor a balanced tree; FIFO/LIFO favor a queue/stack; "smallest/largest next" favors a heap. The wrong choice can turn an O(n) task into O(n²), so this decision often matters more than the algorithm itself.

When should I use a linked list instead of an array?

Rarely in modern code. Arrays (dynamic arrays/lists) win for most cases because O(1) indexing and cache locality make them fast in practice. Choose a linked list when you frequently insert or remove at the ends or splice in the middle at a known node, and you don't need random access — for example, implementing a queue or an LRU cache's recency list. Even then, a deque (array-backed) often suffices and performs better.

Why are hash tables O(1) if they can be O(n) in the worst case?

Hashing distributes keys across buckets so that, with a good hash function and a reasonable load factor, lookups touch only a handful of elements — O(1) on average. The O(n) worst case happens when many keys collide into one bucket (bad hash, or adversarial input). In practice, well-designed hash tables and language built-ins keep collisions rare, so you rely on the average case while being aware the worst case exists (it matters for security-sensitive or adversarial inputs).

What's the difference between a stack and a queue?

Both restrict where you add and remove, but in opposite orders. A stack is LIFO (last-in, first-out) — you push and pop from the same end, like a stack of plates; used for undo, expression parsing, and the call stack. A queue is FIFO (first-in, first-out) — you add at the back and remove from the front, like a line; used for scheduling, buffering, and breadth-first traversal. Both offer O(1) add/remove at their designated ends.