The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Choosing the Right Data Structure

Next ►
►

By the end of the previous module we had covered the course's full catalog of structures: TaskFlow already has a board (arrays and lists), undo (stacks), notifications (queues and heaps), indexes (hash tables), hierarchies (trees) and dependencies (graphs). Now comes the step that separates someone who "knows structures" from someone who "designs with structures": learning to choose. In this lesson we will build a decision method in the form of questions, gather the whole course into one big comparison table, and reason out loud through several interview-style case studies. The perfect structure doesn't exist; what exists is the right structure for your dominant operations.

Contents

  1. The method: choose by operations, not by data
  2. The seven key questions
  3. Decision tree
  4. The course's big table
  5. Worked case studies
  6. Typical choice mistakes and their symptoms
  7. Combining structures: the pattern TaskFlow uses

The method: choose by operations, not by data

The most common junior-developer mistake is to ask "which structure fits this data?". The right question is a different one:

Which operations will I perform most often, and what cost can I afford for each one?

The same data (TaskFlow's tasks, which are dicts with id, title, priority, status...) has lived throughout the course inside lists, stacks, queues, heaps, hash tables, trees and graphs. The data never changed; the dominant operation did:

  • To look up by id: hash table (dict), O(1) average.
  • To undo the last action: stack, O(1) at the end.
  • To serve the highest-priority one: heap, O(log n).
  • To ask for "priority between 1 and 3": BST/AVL, O(log n + k).
  • To order by dependencies: graph + topological order, O(V + E).

The procedure, always the same:

  1. List the problem's operations (insert, search, delete, traverse, minimum, range...).
  2. Estimate how frequent each one is (millions of lookups and few insertions, or the other way around?).
  3. Look up the costs (the big table below) and pick the structure that makes the frequent operations cheap, accepting that the rare ones get more expensive.
  4. If you're torn between two, measure with timeit (module 1): real data has the final word.

The seven key questions

Ask yourself these questions in order. The first one you answer with an emphatic "yes" usually points to the structure.

# Question If the answer is yes... Example in TaskFlow
1 Do I access by exact key (id, name, email)? Hash table: dict / set tasks_by_id[42]
2 Do I need to maintain a total order and run range queries ("between X and Y", "the one after...")? BST/AVL (or bisect over a stable sorted list) "tasks with priority between 1 and 3"
3 Do I only work at the ends? LIFO or FIFO? LIFO → stack; FIFO → queue; both ends → deque undo (LIFO), notifications (FIFO)
4 Do I only care about the highest-priority item at any moment, not the full order? Heap (heapq) UrgentInbox
5 Does the data have a hierarchy (parent-children, containment)? General tree projects → tasks → subtasks
6 Are there many-to-many relationships (dependencies, networks, paths)? Graph the DAG of dependencies between tasks
7 None of the above: just a sequence with access by position or full traversals? list (dynamic array); linked list if there are many mid-list insertions/deletions with a reference to the node the board, on-screen listings

Two important nuances:

  • The questions are not mutually exclusive: a real problem usually answers "yes" to several. That's where the section on combining structures comes in.
  • Questions 2 and 1 are often confused. A hash answers "does key 42 exist?" in O(1), but it cannot answer "which keys lie between 1 and 3?" without scanning everything — that was the hash's limit we hit at the end of module 5, and the door through which trees came in.

Decision tree

The same method, as a diagram. Read it top to bottom and stop at the first leaf that fits:

flowchart TD
    A[Which operation dominates?] --> B{Lookup by<br/>exact key?}
    B -- Yes --> B1{Do I also need<br/>ranges or order?}
    B1 -- No --> H[Hash table: dict / set<br/>O 1 average]
    B1 -- Yes --> T[BST / AVL<br/>O log n]
    B -- No --> C{Do I only work<br/>at the ends?}
    C -- LIFO --> P[Stack<br/>O 1]
    C -- FIFO --> Q[Queue / deque<br/>O 1]
    C -- Both ends --> D[deque<br/>O 1 at both]
    C -- No --> E{Only the highest-<br/>priority item?}
    E -- Yes --> M[Heap heapq<br/>O log n]
    E -- No --> F{Parent-children<br/>hierarchy?}
    F -- Yes --> AR[General tree<br/>traversals O n]
    F -- No --> G{Many-to-many<br/>relationships?}
    G -- Yes --> GR[Graph<br/>BFS/DFS O V+E]
    G -- No --> L{Many mid-list<br/>insertions with a node<br/>in hand?}
    L -- Yes --> LE[Linked list<br/>O 1 with a reference]
    L -- No --> LI[Python list<br/>O 1 access by index]

This tree is a compass, not a law: when the data volume is small (dozens of elements), almost any structure will do and the simplest one wins — which is almost always list or dict.

The course's big table

Every structure we have built or used, with its key operations, when it shines and when it's a trap.

Structure Key operations (Big O) When to use it When NOT to Example in TaskFlow
Array / list access by index O(1); append/pop at the end O(1) amortized; insert/pop(0) O(n); search O(n) Sequences with access by position, traversals, moderate size Many insertions/deletions at the front or middle; frequent searches by value On-screen task listing
Singly linked list insert/delete at the head O(1); access by position O(n) Frequent insertions/deletions at the head; building stacks and queues on top You need access by index or backward traversal The first board (LinkedList, module 2)
Doubly linked list insert/delete with a reference to the node O(1); navigate both ways O(1) per step Forward/backward navigation; deleting a node you have already located When list or deque covers the case with less code The navigable TaskHistory
Circular list advance "to the next" indefinitely O(1) Rotating turns, round-robin Almost any other case TaskDispatcher
Stack push/pop/peek O(1) The last thing in is the first thing that matters: undo, backtracking, parsing You need access to the bottom or to middle positions UndoRedoManager (two stacks)
Queue enqueue/dequeue O(1) Fair arrival order: turns, messaging, BFS The serving order is not the arrival order (→ priority) NotificationQueue
Circular queue (ring buffer) enqueue/dequeue O(1), fixed memory Bounded-size buffers: the last N events The size is not bounded EventLog
Priority queue / heap insert O(log n); extract minimum O(log n); peek minimum O(1) "Always give me the most urgent one"; top-k; schedulers You need to look up arbitrary elements or frequently traverse in full order UrgentInbox with heapq
deque append/pop at both ends O(1); access in the middle O(n) Queues, bounded histories (maxlen), sliding windows Frequent access by index in the middle BoundedHistory, ProductivityWindow
Hash table / dict / set insert/search/delete O(1) average; no order or ranges Access by exact key, counting, grouping, memoizing, deduplicating Ranges, order, "the next one greater than..."; non-hashable keys tasks_by_id, the tag→ids index
BST (unbalanced) insert/search O(log n) average, O(n) worst (degenerate); range O(log n + k) Prototypes, randomly arriving data Data that arrives sorted (it degenerates into a list) The first version of range search
AVL insert/search/delete O(log n) guaranteed; inorder traversal O(n) sorted Order + ranges + predictable performance You only look up by exact key (a hash is simpler and faster) "Priority between 1 and 3" in production
B / B+ tree search/range O(log n) with wide nodes, optimized for disk On-disk indexes, databases In-memory structures (AVL/hash suffice) The SQLite index where TaskFlow would persist
Graph BFS/DFS O(V+E); Dijkstra O((V+E) log V); topological order O(V+E) Dependencies, networks, paths, reachability The data is a plain sequence or a strict hierarchy The dependency DAG, the scheduler

Reading tip: don't memorize the table; memorize the rows that surprise you. That insert(0) on a list is O(n) and that a dict cannot answer range queries are the two facts in this table that prevent the most real-world mistakes.

Worked case studies

Let's reason through four scenarios the way they would come up in a technical interview. Notice that the reasoning always follows the method: operations → frequencies → costs.

Case 1: "Design the autocomplete feature"

When the user types "meet" into TaskFlow's search box, the titles starting with that prefix must appear.

  • Dominant operation: search by prefix, not by exact key. Question 1 (hash) fails: a dict only finds complete keys.
  • Question 2 (order) does fit: in a collection sorted alphabetically, all the titles starting with "meet" are contiguous. With a sorted list and bisect we locate the first candidate in O(log n) and walk forward while the prefix matches.
  • An alternative using what we know about hashing: a dict prefix→list of ids, precomputed (for each title we store all its prefixes). O(1) queries, in exchange for a lot of memory. The structure specialized in this is the trie, which will make an appearance in the resources lesson.
import bisect

def autocomplete(sorted_titles, prefix, limit=10):
    """sorted_titles: list sorted alphabetically."""
    i = bisect.bisect_left(sorted_titles, prefix)  # O(log n)
    results = []
    while i < len(sorted_titles) and sorted_titles[i].startswith(prefix):
        results.append(sorted_titles[i])
        if len(results) == limit:
            break
        i += 1
    return results

bisect_left performs a binary search (the same idea as the BST, over an array): it finds where the prefix would start. After that we just advance while there's a match: O(log n + k) with k results.

Case 2: "The 10 most recent events"

TaskFlow must show the last 10 activity events, discarding the old ones.

  • Operations: add at one end, discard at the other, fixed size. Question 3: ends, FIFO with a bound.
  • This is exactly a ring buffer, and in Python it's already built: deque(maxlen=10). Appending is O(1) and the oldest item is evicted automatically.
from collections import deque

events = deque(maxlen=10)
events.append({"type": "create", "task_id": 7})   # O(1); if there are 10, evicts the oldest

Choosing a list with pop(0) here would work... at O(n) per eviction: the symptom would be an app that slows down as the activity log grows.

Case 3: "Detect whether the project has circular dependencies"

Before scheduling, TaskFlow must warn if A depends on B, B on C, and C on A.

  • "Depends on" is a many-to-many relationship: question 6, graph. A cycle in the dependency graph makes a topological order impossible.
  • The module 7 solution: DFS with three colors (white/gray/black). Finding an edge to a gray node (still on the recursion stack) gives the cycle away. Cost O(V + E). Equivalent alternative: if Kahn's algorithm fails to process every vertex, there is a cycle.
  • The typical mistake is trying to solve this with lists and nested loops "following dependency chains": it ends in O(n²) or in infinite loops. When you see cross-cutting relationships, model the graph explicitly.

Case 4: "Look up by id" versus "list sorted by priority"

TaskFlow needs (a) to open a task by its id instantly and (b) to show the backlog sorted by priority.

  • These are two different dominant operations and no single structure wins at both:
Need dict by id list sorted by priority AVL by priority
Look up by id O(1) O(n) O(n) (the key is the priority, not the id!)
List by priority O(n log n) (sort every time) O(n) (already sorted) O(n) inorder
Insert O(1) O(n) (making room) O(log n)
  • The mature answer: both. A dict id→task as the main store, and a sorted structure (a heap if you only serve the most urgent; an AVL or list+bisect if you list ranges) that holds references. That leads us straight into the last section.

Typical choice mistakes and their symptoms

Every bad choice has a recognizable performance signature. Learn to read it:

Mistake Symptom Diagnosis Fix
Searching by value in a list inside a loop Everything is fine with 100 elements and crawls with 100,000 x in lst is O(n) → the loop is O(n²) set or dict: x in s is O(1)
insert(0) / pop(0) on a list Enqueuing gets slow as the queue grows It shifts every element: O(n) deque (module 4)
Sorting the whole list "to get the minimum" sort() on every iteration: O(n log n) per operation You only need the extreme, not the total order heapq: O(log n)
BST fed data that arrives already sorted "Logarithmic" performance that behaves linearly The tree degenerated into a list AVL, or shuffle / use bisect
dict when you need ranges Code full of for k in d: if a <= k <= b Hashing destroys order on purpose AVL / sorted list + bisect
A graph "simulated" with lists of lists and cross lookups Fragile nested loops, cycles that hang the program Many-to-many relationships left unmodeled Graph with an adjacency list + BFS/DFS
Optimizing without measuring Days lost on an exotic structure for 50 elements Tiny n: the constants dominate timeit first; simple by default

Combining structures: the pattern TaskFlow uses

Real applications almost never use one structure: they use several, coordinated, each one paying for the operation it does best. TaskFlow is the example we have built over eight modules:

import heapq

class TaskFlowCore:
    """Skeleton of how TaskFlow combines structures (minimal version)."""

    def __init__(self):
        self.tasks = {}             # dict id -> task       : lookup by id O(1)
        self.by_tag = {}            # dict tag -> set of ids : inverted index O(1)
        self.urgent = []            # heap (priority, counter, id) : most urgent O(log n)
        self._counter = 0           # stable tie-breaker in the heap

    def create(self, task):
        self.tasks[task["id"]] = task                          # O(1)
        for tag in task.get("tags", []):
            self.by_tag.setdefault(tag, set()).add(task["id"])  # O(1)
        self._counter += 1
        heapq.heappush(self.urgent, (task["priority"], self._counter, task["id"]))  # O(log n)

    def most_urgent(self):
        while self.urgent:
            priority, _, id_ = self.urgent[0]
            task = self.tasks.get(id_)
            # Stale entry: the task was deleted or changed priority
            if task is None or task["priority"] != priority:
                heapq.heappop(self.urgent)   # discard it and keep going
                continue
            return task
        return None

Points of this pattern worth understanding well:

  • The dict is the canonical store: the single source of truth. The other structures hold only ids (cheap references), never copies of the task.
  • The heap uses the (priority, counter, id) tuple from module 4: the counter breaks ties between equal priorities while preserving arrival order, and it prevents comparing dicts.
  • Lazy deletion: removing from the middle of a heap is awkward, so we don't delete; on lookup, we discard entries whose task no longer exists or has changed. It's a standard trick in real schedulers.
  • The price of combining is consistency: every write touches several structures. Centralize modifications in methods (create, delete...) so that no structure falls out of sync.

Exercises

Exercise 1

For each TaskFlow need, choose a structure and justify it with its Big O: (a) check in O(1) whether an email is already registered; (b) show the tasks with hours between 2 and 5; (c) process the user's "undo" actions; (d) hand out tasks among 3 people in rotating turns; (e) a moving average of hours worked over the last 7 days.

Exercise 2

This code finds the unassigned urgent tasks. Identify the two structure-choice problems and rewrite it:

def urgent_unassigned(tasks, assigned):   # tasks: list of dicts; assigned: list of ids
    results = []
    for t in tasks:
        if t["priority"] == 1 and t["id"] not in assigned:
            results.append(t)
    results.sort(key=lambda t: t["hours"])
    return results[:3]

Exercise 3

Design (design only: structures and the cost of each operation, no code) TaskFlow's "review mode": it stores the last 50 visited tasks without duplicates; if you visit one that was already there, it moves up to the most recent position; checking whether a task is in the history must be O(1). Hint: it's the same trade-off as an LRU cache.

Solutions

Exercise 1. (a) set — membership O(1); (b) AVL keyed by hours (or a sorted list + bisect if writes are rare) — range O(log n + k); (c) stack — pure LIFO, O(1); (d) circular list (TaskDispatcher) — endless "next" in O(1); (e) deque(maxlen=7) with an incremental sum — O(1) per day, like module 4's ProductivityWindow.

Exercise 2. Problem 1: t["id"] not in assigned over a list is O(n), which makes the loop O(n·m); convert it once into a set → O(1) per check. Problem 2: sorting everything just to keep 3 is O(k log k); for a small top-k use heapq.nsmallest, O(k log 3):

import heapq

def urgent_unassigned(tasks, assigned):
    assigned_ids = set(assigned)                         # O(m), once
    candidates = [t for t in tasks
                  if t["priority"] == 1 and t["id"] not in assigned_ids]  # O(n)
    return heapq.nsmallest(3, candidates, key=lambda t: t["hours"])       # O(n log 3)

Exercise 3. Combine two coordinated structures: a doubly linked list holding the visit order (most recent at the head) and a dict id→node. Visiting a new task: create a node at the head + an entry in the dict, O(1); if it exceeds 50, remove the node at the tail and its entry from the dict, O(1). Visiting an existing one: the dict locates its node in O(1) and, since the list is doubly linked, it unlinks itself and moves to the head in O(1) — exactly the operation a list cannot do cheaply. Membership check: id in dict, O(1). Neither structure achieves this alone; together, everything is O(1).

Conclusion

You now have the judgment the whole course was aiming for: operations first, then the structure, and when in doubt, measure. The seven questions and the decision tree lead you to a candidate; the big table gives you its costs; the performance symptoms warn you when you got it wrong; and the combination pattern (a dict store + auxiliary indexes and heaps) shows you how real applications do it, TaskFlow included. In the next lesson we'll make the reverse journey: we'll walk back through everything we built, module by module, to consolidate the complete map before the final projects.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved