# Choosing the Right Data Structure — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/p-choose

> Match operations and constraints to the right structure.

## Start from the operations

Pick a data structure by asking **which operations must be fast** and **how much data** there is. Need ordered items, appending and iteration? A **`list`**. Fast membership or de-duplication? A **`set`**. Lookup by key, counting or grouping? A **`dict`**, `Counter` or `defaultdict`. Add and remove at both ends, or a bounded recent history? A **`deque`**. Always the smallest or largest, or top-k? A **heap** (`heapq`). Sorted order with insertions and range queries? `bisect` on a sorted list or **`sortedcontainers`**. Relationships between entities? A **graph** (adjacency lists). Prefix search? A **trie** or sorted list. Merging groups and connectivity? **Union-find**. Repeated expensive computations? A **cache**. Immutable records and keys? **Tuples**, NamedTuples or frozen dataclasses. Large numeric arrays? **`array`** or **NumPy**. Shared between threads? `queue.Queue` and locks. Also consider **read/write ratio** (precompute an index if reads dominate), **memory limits**, **ordering requirements**, **hashability** and whether data fits in memory at all (otherwise use a database). Often the best design combines structures, like a dict plus a heap, or a dict plus a linked list.

## Decision guide

Start from the operation you need most, then pick the structure that makes it fast.

![A simple flowchart with questions such as lookup by key, order needed and smallest first, leading to labelled boxes for dict, list, deque, heap, set and graph.](assets/figures/data-structures-python/section-8-map.svg) — Figure 8.1 — Choosing a structure by its key operation.

## Combining structures: a leaderboard

A dict for O(1) score lookup plus a heap for top-k queries.

```python
import heapq

class Leaderboard:
    """Fast score updates by player, and fast top-k queries."""

    def __init__(self) -> None:
        self.scores: dict[str, int] = {}             # player -> current score

    def add_points(self, player: str, points: int) -> None:     # O(1)
        self.scores[player] = self.scores.get(player, 0) + points

    def top(self, k: int) -> list[tuple[str, int]]:             # O(n log k)
        return heapq.nlargest(k, self.scores.items(), key=lambda item: item[1])

    def rank(self, player: str) -> int:                          # O(n): fine for occasional use
        score = self.scores[player]
        return 1 + sum(1 for s in self.scores.values() if s > score)

board = Leaderboard()
for player, pts in [("asha", 50), ("ravi", 30), ("meera", 70), ("asha", 40), ("kabir", 10)]:
    board.add_points(player, pts)

print(board.top(3))          # [('asha', 90), ('meera', 70), ('ravi', 30)]
print(board.rank("meera"))   # 2
# If rank queries became frequent, a SortedList of (-score, player) would make them O(log n).
```

## Write down the operations and their frequency

Before choosing, list operations such as "add score: 10,000 per second; top 10: once per second; rank of one player: rare". The frequencies usually make the right structure obvious.

**Quiz:** Which structure best supports adding and removing items at both ends in O(1)?

- [ ] list
- [ ] set
- [x] collections.deque
- [ ] tuple

*Answer:* collections.deque. deque is designed for efficient operations at both ends.