Choosing the Right Data 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.

Combining structures: a leaderboard

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

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.

त्वरित जाँच: Which structure best supports adding and removing items at both ends in O(1)?

• list
• set
• collections.deque
• tuple