Loading learning content...
We've established that different data structures optimize for different operations. Now it's time to get precise. This page presents a comprehensive, side-by-side analysis of operation costs across all major data structures.
This isn't just a reference table—it's a decision-making framework. By understanding why each data structure has its particular cost profile, you'll develop the intuition to select the right structure for any problem, even structures you haven't encountered before.
The goal: After this page, given any problem's operation requirements, you should be able to identify candidate data structures and immediately eliminate unsuitable ones based on their cost profiles.
You will master the complete operation cost matrix for arrays, linked lists, hash tables, trees, heaps, and more. More importantly, you'll understand the underlying reasons for each cost—the physical and logical properties that determine performance. This transforms rote memorization into deep understanding.
Let's begin with a comprehensive overview. This table summarizes the time complexity of core operations across the most important data structures. Study it carefully—this is the foundation of every data structure decision you'll make.
Legend:
| Data Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array (Static) | O(1) | O(n) | N/A (fixed) | N/A (fixed) | O(n) |
| Array (Dynamic) | O(1) | O(n) | O(1) amort.* | O(n) | O(n) |
| Sorted Array | O(1) | O(log n) | O(n) | O(n) | O(n) |
| Singly Linked List | O(n) | O(n) | O(1)** | O(1)** | O(n) |
| Doubly Linked List | O(n) | O(n) | O(1)** | O(1)** | O(n) |
| Hash Table | N/A | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Binary Search Tree | N/A | O(log n)*** | O(log n)*** | O(log n)*** | O(n) |
| AVL/Red-Black Tree | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| Binary Heap | O(1)† | O(n) | O(log n) | O(log n)† | O(n) |
| Stack | O(1)‡ | O(n) | O(1) | O(1) | O(n) |
| Queue | O(1)‡ | O(n) | O(1) | O(1) | O(n) |
Table Notes:
*Dynamic array insert is O(1) amortized for append; O(n) for arbitrary position.
**Linked list insert/delete is O(1) only if you already have a pointer to the position. Finding the position first makes it O(n).
***BST complexities assume a balanced tree. An unbalanced BST degenerates to O(n).
†Heap provides O(1) access to root (min or max) only. Deletion refers to extracting the root.
‡Stack/Queue access is O(1) for top/front only — by design, not all elements are accessible.
When a cell shows 'N/A', it means the operation doesn't make sense for that structure (e.g., 'Access by index' for a hash table). When it shows 'O(n)', the operation is possible but expensive. This distinction matters: N/A means you need a different approach; O(n) means you can do it, but perhaps shouldn't for large n.
The complexity differences in our table aren't arbitrary—they emerge from fundamental properties of how data is organized in memory. Understanding these underlying causes transforms the table from something to memorize into something you can derive.
Three Properties That Determine Performance:
Contiguous Memory (Arrays):
Memory addresses: 1000 1004 1008 1012 1016 1020
Array elements: [A] [B] [C] [D] [E] [F]
↑
base address
To access element[i]: base + (i × size) = direct calculation
Result: O(1) access
Why this enables O(1) access: The CPU can compute the exact memory address of any element using simple arithmetic. No traversal needed.
Scattered Memory (Linked Structures):
Memory addresses: 1000 2048 1536 3072
Linked nodes: [A|→] → [B|→] → [C|→] → [D|null]
head
To access element[2]:
Start at head (1000)
Follow pointer to 2048
Follow pointer to 1536
Now at element[2]
Why this forces O(n) access: Each element only knows where the next element is. To reach element i, you must traverse i pointers sequentially.
Contiguous memory is also cache-friendly: accessing one element often brings nearby elements into the CPU cache. Scattered memory causes cache misses on every pointer follow. This means arrays are often even faster than O(1) vs O(n) suggests—the constant factors favor contiguous structures.
The Fundamental Principle:
Every data structure's operation costs can be derived from these three properties:
| Property | What It Enables | What It Costs |
|---|---|---|
| Contiguous memory | O(1) random access | Expensive mid-insertions |
| Sorted order | O(log n) binary search | O(n) or O(log n) maintaining order |
| Direct addressing (hashing) | O(1) key lookup | No ordering, no range queries |
| Tree structure | O(log n) balanced operations | Pointer overhead, balancing complexity |
| Sequential links | O(1) local mutations | O(n) random access |
Arrays are the most fundamental data structure, and understanding their cost profile in depth illuminates why other structures exist.
Core Properties:
The Array Superpower: O(1) random access to any element by index.
| Operation | Time | Why This Complexity | When It Matters |
|---|---|---|---|
| Access by index | O(1) | Direct address calculation: base + i × size | Always fast, no caveats |
| Search (unsorted) | O(n) | Must check each element until found | Problematic for large arrays searched often |
| Search (sorted) | O(log n) | Binary search halves space each step | Requires sorted maintenance |
| Insert at end | O(1) amortized | Just place at size index; occasional O(n) resize | Excellent for append-heavy workloads |
| Insert at start | O(n) | Must shift all n elements right | Avoid if front-insertion is frequent |
| Insert at middle | O(n) | Must shift n/2 elements on average | Avoid if mid-insertion is common |
| Delete at end | O(1) | Just decrement size | Excellent for stack-like usage |
| Delete at start | O(n) | Must shift all remaining elements left | Avoid if front-deletion is frequent |
| Delete at middle | O(n) | Must shift elements to fill gap | Avoid if arbitrary deletion is common |
| Find min/max | O(n) | Must scan all elements (unsorted) | Consider heap if frequent |
| Traverse all | O(n) | Visit each element once | Very cache-friendly, fast constant factors |
Arrays are optimal when: (1) You need random access by index, (2) Data is relatively static or append-only, (3) Cache performance matters (traversal), (4) Memory efficiency matters (no pointer overhead). The common case—read-heavy, append-only data—is exactly what arrays handle best.
When Arrays Fail:
Linked lists trade away random access for efficient local mutations. Understanding when this trade-off pays off is crucial.
Core Properties:
The Linked List Superpower: O(1) insertion/deletion at any position where you already have a pointer.
| Operation | Time | Why This Complexity | Critical Caveat |
|---|---|---|---|
| Access by index | O(n) | Must traverse n links | This is the fundamental weakness |
| Search | O(n) | Must traverse until found | Cannot use binary search even if sorted |
| Insert at head | O(1) | Create node, point to old head, update head | Best case for frequent front insertions |
| Insert at tail (with tail ptr) | O(1) | Create node, link from tail, update tail | Requires maintaining tail pointer |
| Insert at tail (no tail ptr) | O(n) | Must traverse to find last node | Common implementation oversight |
| Insert after known node | O(1) | Pointer surgery only | Powerful IF you have the pointer |
| Delete head | O(1) | Update head to head.next | Best case |
| Delete tail (singly linked) | O(n) | Must traverse to find second-to-last | Doubly linked solves this |
| Delete tail (doubly linked) | O(1) | Tail.prev becomes new tail | DLL trades memory for this |
| Delete known node | O(1) | Pointer surgery only | Requires pointer to node |
| Find min/max | O(n) | Must traverse all nodes | No better than array |
| Traverse all | O(n) | Visit each node once | Poor cache locality |
"Linked lists have O(1) insertion." This is only true if you already have a pointer to the insertion location. If you need to find the location first, total time = O(n) search + O(1) insert = O(n). Be precise about assumptions.
Hash tables achieve the seemingly magical O(1) average-case lookup by converting keys directly into array indices. Understanding their cost profile—including the caveats—is essential.
Core Properties:
The Hash Table Superpower: O(1) average-case insert, delete, and lookup by key.
| Operation | Average | Worst | Why Worst Case Happens |
|---|---|---|---|
| Search by key | O(1) | O(n) | All keys hash to same bucket (pathological) |
| Insert | O(1) | O(n) | All collide, or resize triggers full rehash |
| Delete by key | O(1) | O(n) | All keys in same bucket (pathological) |
| Access by index | N/A | N/A | Hash tables have no concept of position |
| Find min/max | O(n) | O(n) | Must check all entries — no ordering |
| Range query | O(n) | O(n) | Must check all entries — no ordering |
| Get sorted order | O(n log n) | O(n log n) | Must extract all + sort |
| Iterate (all elements) | O(n) | O(n) | Visit all buckets and entries |
Understanding the O(1) Average Case:
Hash tables achieve O(1) under these conditions:
Lookup process (average case):
hash(key) = 42 → O(1) hash computation
bucket = 42 % table_size → O(1) index
search bucket for key → O(1) if ~1 entry per bucket
Total: O(1)
When O(1) Becomes O(n):
If many keys hash to the same bucket (collisions), that bucket becomes a linked list:
buckets[7] → [key_a] → [key_b] → [key_c] → ... → [key_n]
Searching for key_n requires traversing the entire chain → O(n)
This pathological case is rare with good hash functions but possible (e.g., HashDoS attacks).
Hash tables CANNOT efficiently: (1) Find min/max, (2) Answer range queries ('all users aged 25-35'), (3) Provide sorted iteration, (4) Find the 'next' or 'previous' key, (5) Support any operation that requires ordering. If you need ANY of these, a hash table is immediately disqualified.
Space Overhead:
Hash tables trade space for time:
For memory-constrained environments, this overhead may disqualify hash tables.
Trees provide a middle ground: O(log n) operations while maintaining sorted order. This combination is often exactly what's needed.
Core Properties:
The Tree Superpower: O(log n) search, insert, delete WHILE maintaining sorted order.
| Operation | Time | Why This Complexity | Unbalanced Worst Case |
|---|---|---|---|
| Search | O(log n) | Height is log n; one comparison per level | O(n) if degenerate |
| Insert | O(log n) | Search for position + O(1) insertion | O(n) if degenerate |
| Delete | O(log n) | Search + restructure (may require successor) | O(n) if degenerate |
| Find minimum | O(log n) | Go left until null | O(n) if left-skewed |
| Find maximum | O(log n) | Go right until null | O(n) if right-skewed |
| Range query [a, b] | O(log n + k) | Navigate to 'a', in-order traverse until 'b' | O(n) if degenerate |
| In-order traversal | O(n) | Visit all nodes (gives sorted order) | O(n) regardless |
| Kth smallest element | O(log n)* | Augment with subtree sizes | Requires augmentation |
The Balance Problem:
A BST is only O(log n) if balanced. Without balancing, sequential insertions degenerate into a linked list:
Insert 1, 2, 3, 4, 5 into BST:
1
\
2
\
3 ← This is a linked list, not a tree!
\
4
\
5
Height = n, so all operations become O(n)
Self-Balancing Trees (AVL, Red-Black):
These variants maintain balance through rotations after insert/delete:
Both guarantee O(log n) operations in all cases.
Choose trees over hash tables when: (1) You need sorted iteration, (2) You need range queries, (3) You need min/max quickly, (4) You need predecessor/successor queries, (5) Worst-case guarantees matter (O(log n) vs O(n)). Choose hash tables when you only need point queries and ordering doesn't matter.
Heaps are specialized trees optimized for one thing: quickly accessing and removing the extreme value (min or max). They sacrifice general search for this specialized capability.
Core Properties:
The Heap Superpower: O(1) access to min/max + O(log n) extract-min/max + O(log n) insert.
| Operation | Time | Why This Complexity | Key Insight |
|---|---|---|---|
| Find min (min-heap) | O(1) | Root is always minimum | This is the whole point |
| Find max (max-heap) | O(1) | Root is always maximum | This is the whole point |
| Find max (min-heap) | O(n) | Max is somewhere in leaves; must scan all | Heap doesn't help for non-extreme |
| Insert | O(log n) | Add at end, bubble up to restore property | Height is log n |
| Extract min/max | O(log n) | Remove root, move last to root, bubble down | Must restore heap property |
| Delete arbitrary | O(n) | Must first find element (O(n)), then O(log n) restructure | Search is the bottleneck |
| Decrease key (min-heap) | O(log n) | Update value, bubble up | Important for Dijkstra's algorithm |
| Increase key (max-heap) | O(log n) | Update value, bubble up | Priority queue update |
| Build heap from array | O(n) | Bottom-up heapify is linear | Not O(n log n) — surprisingly efficient |
Why Heaps Aren't Good for Search:
Min-heap with values [1, 3, 2, 7, 6, 4, 5]:
1 ← root is minimum
/ \
3 2 ← 3 and 2 are both children of 1
/ \ / \
7 6 4 5 ← where is 5? Could be anywhere in the leaves
Q: Is 4 in this heap?
A: We must check potentially every node.
4 < 1? No. (Can't use BST logic)
Check all children of 1? Still need to check everything.
The heap property only guarantees parent-child relationships, not left-right ordering like BST. This means no binary search.
When Heaps Excel:
Both heaps and BSTs can find min/max in O(log n) for BST or O(1) for heap. The key difference: heaps are optimized for repeated extract-min/max (O(log n) each), while BSTs maintain full sorted order. Use heaps for priority queues; use BSTs when you need general queries.
Let's consolidate this knowledge with concrete scenarios. For each scenario, we'll identify the dominant operations and show how they guide structure selection.
Scenario 1: Implementing a Phonebook
Operations:
| Structure | Search | Insert | Sorted List | Verdict |
|---|---|---|---|---|
| Unsorted Array | O(n) ✗ | O(1) ✓ | O(n log n) ✗ | Search too slow |
| Sorted Array | O(log n) ✓ | O(n) ✗ | O(n) ✓ | Insert too slow |
| Hash Table | O(1) ✓ | O(1) ✓ | O(n log n) ✗ | Good if sorting rare |
| Balanced BST | O(log n) ✓ | O(log n) ✓ | O(n) ✓ | Best all-around |
Optimal choice: Balanced BST (or ordered map) — handles all operations efficiently.
Scenario 2: Implementing an Undo Stack
Operations:
| Structure | Push | Pop | Verdict |
|---|---|---|---|
| Array (end) | O(1) ✓ | O(1) ✓ | Perfect — use dynamic array as stack |
| Linked List (head) | O(1) ✓ | O(1) ✓ | Also works, more overhead |
| Hash Table | N/A | N/A | Wrong structure entirely |
Optimal choice: Dynamic array (used as stack) — simple, efficient, cache-friendly.
Scenario 3: Implementing a Task Scheduler (by Priority)
Operations:
| Structure | Insert | Extract-Max | Change Priority | Verdict |
|---|---|---|---|---|
| Unsorted Array | O(1) | O(n) ✗ | O(n) ✗ | Extract too slow |
| Sorted Array | O(n) ✗ | O(1) | O(n) ✗ | Insert too slow |
| Max-Heap | O(log n) ✓ | O(log n) ✓ | O(log n)* ✓ | Optimal for priority queue |
| Balanced BST | O(log n) ✓ | O(log n) ✓ | O(log n) ✓ | Works, more overhead |
Optimal choice: Max-Heap — purpose-built for priority queues. *Note: change-priority is O(log n) if you maintain a hash map from task ID to heap position.
Scenario 4: Detecting Duplicate Entries
Operations:
| Structure | Search | Insert | Verdict |
|---|---|---|---|
| Array | O(n) ✗ | O(1) | Search disqualifies |
| Sorted Array | O(log n) | O(n) ✗ | Insert disqualifies |
| Hash Set | O(1) ✓ | O(1) ✓ | Perfect for membership testing |
| Balanced BST (Set) | O(log n) | O(log n) | Works, slower than hash |
Optimal choice: Hash Set — O(1) for both critical operations. BST would work but hash is 10-100x faster in practice.
In every scenario: (1) Identify dominant operations, (2) Find structures with optimal complexity for those operations, (3) Verify no disqualifying costs for secondary operations, (4) Choose simplest solution among candidates. This systematic approach works for any problem.
We've now built a comprehensive understanding of how operation costs vary across data structures. Let's consolidate the key insights:
Quick Selection Guide:
| If You Need... | Consider First |
|---|---|
| O(1) random access by index | Array |
| O(1) lookup by key | Hash Table |
| O(log n) lookup with ordering | Balanced BST |
| O(1) access to min/max | Heap |
| O(1) front insert/delete | Deque or Linked List |
| Frequent mid-structure mutations | Linked List |
| Range queries | BST or Sorted Array |
| Memory efficiency | Array (no pointers) |
You now understand not just WHAT the operation costs are, but WHY they are what they are. This deeper understanding lets you reason about new structures you haven't seen before. Next, we'll apply this knowledge to concrete problems — seeing how one problem can be solved with multiple structures, each with different trade-offs.