# 4 Data Structures Every Developer Should Master

> The four data structures every developer needs: arrays, hash tables, stacks and queues, and trees, with Python examples and Big-O analysis.

- Author: Shawn Ng (https://shawnng.com/about)
- Published: 2025-12-28
- Updated: 2026-09-20
- Canonical URL: https://shawnng.com/posts/data-structures-every-developer-should-master
- Topics: data-structures, algorithms, software-engineering, computer-science

## Key takeaways

- Arrays give O(1) access by index but O(n) insertion at the beginning, because every later element has to shift.
- Hash tables give O(1) average lookup, insert and delete, degrading to O(n) only when every key collides into one bucket.
- Stacks are last in, first out and queues are first in, first out, and both push, pop and peek in O(1).
- A balanced binary search tree searches, inserts and deletes in O(log n), but degrades to O(n) when it becomes unbalanced.
- Use an array for access by position, a hash table for access by key, and a tree for sorted data with fast search.

You do not need to memorize every data structure in existence. But there are four that show up so often in real-world code that mastering them will make you a dramatically better developer. In this post, we will break down arrays, hash tables, stacks and queues, and trees, covering when to reach for each, their time complexity trade-offs, and practical applications.

Check out the full video on my YouTube channel [Divide and Quantum](https://www.youtube.com/watch?v=8umwYHi9AFg).

## Why These Four?

Every complex data structure is built on top of simpler ones. Databases use B-trees. Caches use hash tables. Undo systems use stacks. If you deeply understand these four primitives, you will be able to reason about almost any system you encounter.

## Arrays: The Foundation

An array is a contiguous block of memory where elements are stored sequentially. This simple layout gives arrays a superpower: **constant-time random access**. If you know the index, you can jump directly to that element.

### Time Complexity

| Operation | Average Case |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Insert at end | O(1) amortized |
| Insert at beginning | O(n) |
| Delete by index | O(n) |

### When to Use Arrays

Arrays are your default choice when you need ordered data and frequent random access. Think of leaderboards, time-series data, or any list you iterate over from start to finish.

```python
# Arrays shine when you need fast index-based access
scores = [95, 82, 91, 78, 88]

# O(1) access - jump straight to the third score
third_score = scores[2]  # 91

# Appending is fast (amortized O(1) in Python lists)
scores.append(73)

# But inserting at the start is expensive - every element shifts
scores.insert(0, 99)  # O(n) operation
```

### The Hidden Advantage: Cache Friendliness

Because array elements sit next to each other in memory, CPUs can load them into [cache lines](https://shawnng.com/posts/cache-misses-performance-killer) efficiently. This means iterating over an array is significantly faster in practice than iterating over a linked list, even though both are O(n) in theory. The constant factor matters.

## Hash Tables: O(1) Lookup Power

A hash table maps keys to values using a [hash function](https://shawnng.com/posts/hash-tables-how-they-work). Python dictionaries, JavaScript objects, and Java HashMaps are all hash tables under the hood, which is why they show up in every layer of a [MEAN stack application](https://shawnng.com/posts/mean-stack-developer), from Mongo's indexes to Node's object literals.

### Time Complexity

| Operation | Average Case | Worst Case |
|---|---|---|
| Lookup | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |

The worst case happens when every key collides into the same bucket, but with a good hash function, this is extremely rare.

### When to Use Hash Tables

Reach for a hash table when you need fast lookups by key, when counting occurrences, or when you need to detect duplicates.

```python
# Counting word frequencies - classic hash table use case
def word_frequency(text):
    freq = {}
    for word in text.lower().split():
        freq[word] = freq.get(word, 0) + 1
    return freq

text = "the cat sat on the mat the cat"
print(word_frequency(text))
# {'the': 3, 'cat': 2, 'sat': 1, 'on': 1, 'mat': 1}

# Two-sum problem: find two numbers that add up to a target
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:  # O(1) lookup
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
```

The two-sum example perfectly illustrates the hash table advantage. A brute-force approach checks every pair in O(n^2). With a hash table, you solve it in a single O(n) pass.

## Stacks and Queues: Order Matters

Stacks and queues are both linear data structures, but they differ in one crucial way: the order elements come out.

- **Stack** (LIFO): Last In, First Out. Think of a stack of plates.
- **Queue** (FIFO): First In, First Out. Think of a line at a coffee shop.

### Time Complexity (Both)

| Operation | Time |
|---|---|
| Push / Enqueue | O(1) |
| Pop / Dequeue | O(1) |
| Peek | O(1) |

### Stack in Action: Balanced Parentheses

One of the most common interview questions and a genuinely useful real-world pattern.

```python
def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()

    return len(stack) == 0

print(is_balanced("{[()]}"))   # True
print(is_balanced("{[(])}"))   # False
print(is_balanced("((()"))     # False
```

### Queue in Action: Breadth-First Search

Queues are essential for BFS, task scheduling, and message processing systems like Kafka and RabbitMQ.

```python
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()  # O(1) with deque
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return order

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
```

Note the use of `collections.deque` instead of a regular list. A list's `pop(0)` is O(n) because it shifts every remaining element. A deque gives you O(1) pops from both ends.

Swap that queue for a priority queue and the same traversal becomes [Dijkstra's shortest-path algorithm](https://shawnng.com/posts/dijkstras-algorithm-explained).

## Trees: Hierarchical Data Done Right

Trees are non-linear data structures where each node has zero or more children. The most practical variant for developers is the **binary search tree (BST)**, where the left child is always smaller and the right child is always larger.

### Time Complexity (Balanced BST)

| Operation | Average Case | Worst Case (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |

The worst case happens when the tree degenerates into a linked list, which is why self-balancing trees like AVL trees and Red-Black trees exist.

### Building a Simple BST

```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        self._insert(self.root, val)

    def _insert(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)
        else:
            if node.right is None:
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None:
            return False
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

tree = BST()
for val in [8, 3, 10, 1, 6, 14]:
    tree.insert(val)

print(tree.search(6))   # True
print(tree.search(7))   # False
```

### Where Trees Show Up

Trees are everywhere once you start looking. File systems are trees. The DOM in your browser is a tree. Database indexes use B-trees, a self-balancing variant that minimizes disk reads. Compilers parse your code into abstract syntax trees. Even your router uses a trie, a specialized tree, to match URL patterns.

## Choosing the Right Data Structure

Here is a quick decision framework:

- **Need fast access by position?** Use an array.
- **Need fast access by key?** Use a hash table.
- **Need to process items in a specific order (LIFO/FIFO)?** Use a stack or queue.
- **Need sorted data with fast insert, delete, and search?** Use a tree.

The best developers do not just know these data structures exist. They develop an intuition for which one fits the problem at hand. That intuition comes from practice, and it starts with understanding the fundamentals covered here.

## Frequently asked questions

### What data structures should every developer know?

Arrays, hash tables, stacks and queues, and trees. Every more complex structure is built on these four: databases use B-trees, caches use hash tables, and undo systems use stacks.

### When should I use a hash table instead of an array?

Use a hash table when you look values up by key, count occurrences, or detect duplicates, because those are O(1) on average. Use an array when you need ordered data and fast access by index.

### Why is iterating an array faster than a linked list if both are O(n)?

Array elements sit next to each other in memory, so the CPU loads them into cache lines efficiently. A linked list scatters its nodes, so the constant factor is far worse even though the complexity is identical.

### Why use collections.deque instead of a list for a queue in Python?

A list's pop(0) is O(n) because every remaining element shifts down. A deque gives you O(1) pops from both ends, which is what breadth-first search and task queues need.

## Sources

- R. Bayer, E. M. McCreight (1972). [Organization and maintenance of large ordered indexes](https://doi.org/10.1007/BF00288683). Acta Informatica.
- Leo J. Guibas, Robert Sedgewick (1978). [A dichromatic framework for balanced trees](https://doi.org/10.1109/SFCS.1978.3). 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), IEEE.
- Edward Fredkin (1960). [Trie memory](https://doi.org/10.1145/367390.367400). Communications of the ACM.
- Python Software Foundation. [deque objects](https://docs.python.org/3/library/collections.html#deque-objects). Python 3 documentation (collections module).
- Python Wiki contributors. [TimeComplexity](https://wiki.python.org/moin/TimeComplexity). Python Software Foundation.