Data Structures Comparison Guide: When to Use What

Knowing how a data structure works is step one. The real skill is knowing when to use it. In interviews and system design, the first question is always the same: “Which data structure fits this problem?”

This guide gives you head-to-head comparisons, complexity tables, and a decision flowchart. Bookmark it. Come back to it before interviews. Use it as your mental index into the world of data structures.

1. Array vs LinkedList vs Deque

These are the three fundamental sequential containers. Each makes a different trade-off.

When to use each

Array (contiguous in memory):
┌───┬───┬───┬───┬───┐
│ 3 │ 1 │ 4 │ 1 │ 5 │  → CPU cache loves this
└───┴───┴───┴───┴───┘
LinkedList (scattered in memory):
[3|→]  …  [1|→]  …  [4|→]  …  [1|→]  [5|∅]
↑ cache miss  ↑ cache miss  ↑ cache miss

Decision guide

• Default choice: Array. It is the fastest, simplest, and most cache-friendly.
• Need O(1) front insertion/deletion: Deque.
• Need O(1) middle insertion with a pointer to the node: LinkedList.
• Building a queue: Deque.
• Implementing LRU cache: LinkedList (for O(1) move-to-front) + HashMap.

Real-world: arrays back 90% of all data structures. Even “linked” structures like trees are often stored in arrays for cache performance (binary heap = array).

2. HashMap vs TreeMap vs Trie

All three map keys to values, but with very different performance profiles.

Comparison table

Decision guide

• Need fast lookup by exact key: HashMap. It is the default.
• Need keys in sorted order or range queries: TreeMap.
• Need prefix search (“find all words starting with ‘pre’”): Trie.
• Keys are integers in a small range: plain array (index = key).

# HashMap: O(1) lookup
from collections import defaultdict
word_count = defaultdict(int)
for word in words:
    word_count[word] += 1

# TreeMap equivalent in Python: SortedDict from sortedcontainers
from sortedcontainers import SortedDict
sd = SortedDict()
sd["apple"] = 1
sd["banana"] = 2
# sd.irange("a", "b") → keys in range ["a", "b"]

# Trie: O(L) prefix search
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Interview tip: when someone says “design autocomplete,” the answer is Trie (or a similar prefix structure). When they say “design a cache,” the answer starts with HashMap.

3. Heap vs Sorted Array vs BST

All three maintain some notion of order, but each is optimised for different access patterns.

Comparison table

Decision guide

• Need the min or max repeatedly: Heap. It is purpose-built for this.
• Need both min and max: two heaps (min-heap + max-heap), or a balanced BST.
• Data is static, need k-th element: Sorted array.
• Need fast insert + delete + search: Balanced BST.
• Building a priority queue: Heap.

import heapq

# Heap: perfect for "give me the smallest element"
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
print(heapq.heappop(pq))  # 2

# Sorted array: perfect for binary search
arr = [1, 3, 5, 7, 9]
import bisect
idx = bisect.bisect_left(arr, 5)  # O(log n) search

Classic interview problem: “Find the median of a stream” → use two heaps (max-heap for lower half, min-heap for upper half).

4. Stack vs Queue vs Priority Queue

Three containers with different access policies.

When to use each

• Stack: problems involving nesting (parentheses, HTML tags), most recent element (undo/redo), DFS (explicit stack), monotonic stack (next greater element).
• Queue: BFS (level-by-level traversal), task scheduling (FIFO fairness), rate limiting (sliding window of requests).
• Priority Queue: always need the best/worst element (Dijkstra’s algorithm, merge k sorted lists, event simulation), scheduling by priority (OS task scheduler).

Stack:          Queue:          Priority Queue:
┌───┐          ┌───────────┐    ┌───┐
│ 3 │ ← top    │ 1 2 3 4 5 │    │ 1 │ ← min (always the best)
│ 2 │          └───────────┘    │ 3 │
│ 1 │          front → out      │ 5 │
└───┘                           │ 7 │
top → out                       └───┘

5. Set vs BitSet vs Bloom Filter

All three answer the question “is this element in the collection?”

Decision guide

• Default membership test: HashSet.
• Elements are integers in [0, N] and N is manageable: BitSet (extremely space-efficient).
• Space is critical and false positives are acceptable: Bloom Filter.

# HashSet: general purpose
seen = set()
seen.add("apple")
print("apple" in seen)  # True

# BitSet: for integer elements in a known range
class BitSet:
    def __init__(self, size):
        self.bits = [0] * ((size >> 5) + 1)

    def add(self, x):
        self.bits[x >> 5] |= (1 << (x & 31))

    def contains(self, x):
        return bool(self.bits[x >> 5] & (1 << (x & 31)))

bs = BitSet(1000)
bs.add(42)
print(bs.contains(42))  # True
print(bs.contains(43))  # False

Interview example: “Check if a character has been seen” with only lowercase letters → use a 26-bit integer as a BitSet.

6. Graph Representations: Adjacency List vs Matrix

Decision guide

• Most real-world graphs (social networks, road maps): Adjacency list. They are sparse.
• Dense graphs or need O(1) edge lookup: Adjacency matrix.
• Weighted edges: Adjacency list with (neighbour, weight) tuples, or matrix with weights as values.

# Adjacency list (most common)
from collections import defaultdict
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)
graph[1].append(2)

# Adjacency matrix
n = 5
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = 1  # edge from 0 to 1
matrix[0][2] = 1  # edge from 0 to 2

Comprehensive Comparison Table

Here is every major data structure at a glance:

*Array append is O(1) amortised. **LinkedList O(1) with pointer to node.

The “Which Data Structure?” Decision Flowchart

When you face a new problem, ask these questions in order:

Do I need key-value mapping?
├─ Yes → Need ordering? → Yes → TreeMap
│                       → No  → HashMap
└─ No → Continue


Do I need to maintain order of insertion?
├─ LIFO → Stack
├─ FIFO → Queue
├─ By priority → Heap / Priority Queue
└─ No specific order → Continue


Do I need fast membership testing?
├─ Elements are small integers → BitSet
├─ Approximate OK → Bloom Filter
└─ Exact → HashSet


Do I need sorted data?
├─ Static (no inserts) → Sorted Array
├─ Dynamic → Balanced BST / TreeSet
└─ No → Array or LinkedList


Is it a graph problem?
├─ Sparse → Adjacency List
└─ Dense → Adjacency Matrix


Need range queries?
├─ Static → Sparse Table (min/max) or Prefix Sum (sum)
└─ Dynamic → Segment Tree or Fenwick Tree

Real-World Mapping

Interview Tips

When the interviewer says… you should think…

• “Find the k most frequent…” → HashMap (count) + Heap (top k)
• “Find if a path exists…” → Graph + BFS/DFS
• “Design an LRU cache…” → HashMap + Doubly LinkedList
• “Find the median in a stream…” → Two Heaps
• “Implement autocomplete…” → Trie
• “Check for balanced parentheses…” → Stack
• “Find shortest path…” → Graph + BFS (unweighted) or Dijkstra (weighted)
• “Range sum queries with updates…” → Segment Tree or Fenwick Tree

The meta-strategy

1. Start with the simplest structure (array, hash map). Most problems can be solved with these.
2. Upgrade only when needed. Need ordering? Switch from HashMap to TreeMap. Need fast min? Add a Heap.
3. Combine structures for complex requirements. LRU cache = HashMap + LinkedList. Median of stream = two Heaps.

Recap

Choosing the right data structure is the most impactful decision in any coding problem:

• Arrays are the default — fast, simple, cache-friendly
• HashMaps provide O(1) lookup for unordered data
• TreeMaps/BSTs maintain sorted order with O(log n) operations
• Heaps give you the min/max in O(1) with O(log n) updates
• Tries excel at prefix-based operations on strings
• Stacks, queues, and priority queues enforce specific access orders
• Graph representations depend on density

The right data structure makes the right algorithm obvious. The wrong data structure makes every algorithm painful.

Next steps

See these data structures in action in real systems: DSA in Real Systems. For interview preparation strategy, see Problem Solving Framework.

Questions or feedback? Email codeloomdevv@gmail.com.