In the previous lesson you learned to choose structures with judgment; in this one we'll look back calmly. We'll review the entire course by telling it as what it has really been: the story of TaskFlow, an application that started out as a plain Python dictionary and ended up with a board, undo, notifications, indexes, hierarchies and a dependency scheduler. Seeing the whole journey at once fixes the mental map better than any list of definitions, and the final self-assessment quiz will tell you honestly what you have down cold and what deserves a review before the projects.

1. The evolution of TaskFlow, module by module
2. Cheat-sheet table: everything we've built
3. The five cross-cutting concepts
4. What you can do now that you couldn't before
5. Self-assessment quiz

TaskFlow was born as a humble dict: {"id": 1, "title": "...", "priority": 2, "status": "pending"}. Before building anything we learned to think: the difference between an ADT's contract and its implementation, Big O notation from O(1) to O(n²), the cost table for list/dict/set, and how to actually measure with timeit. We also looked memory in the eye: an array is pure contiguity (base + i × size, hence O(1) access), Python's list is a dynamic array, and insert(0)/pop(0) hide an O(n) we would chase for the rest of the course.

The first real problem: inserting and removing tasks from the board without paying for shifts. With Node and LinkedList we built TaskFlow's board and accepted the linked-list bargain: O(1) insertion at the head in exchange for O(n) access by position. DoubleNode and DoublyLinkedList gave us the TaskHistory, navigable in both directions, and the CircularList gave us the round-robin TaskDispatcher. As a bonus, the classics: reversing the list, detecting cycles with Floyd's algorithm (tortoise and hare), merging sorted lists and insert_sorted.

"Ctrl+Z" is the star operation of any editor, and its structure is the stack: the last thing you did is the first thing that gets undone. On top of Stack and LinkedStack we assembled the ActionHistory and the UndoRedoManager with two stacks (undo pushes onto redo, and vice versa). We saw that stacks also validate (is_balanced_filter), compute (eval_postfix, infix_to_postfix), remember extremes (MinStack) and hold up the program's very execution: the call stack explains recursion, RecursionError, and how to turn recursion into iteration with an explicit stack.

Notifications demanded FIFO fairness: Queue on top of LinkedList gave us the NotificationQueue, and along the way we proved that two stacks make a queue (TwoStackQueue). The CircularQueue (ring buffer) solved the EventLog with fixed memory. When "in arrival order" stopped being enough, priority queues arrived: from the naive version to heapq with (priority, counter, task) tuples in the UrgentInbox. And collections.deque proved to be the Swiss Army knife of the ends: BoundedHistory with maxlen, the moving-average ProductivityWindow, and the monotonic deque.

Finding a task by id by walking lists was O(n); the O(1) magic of dict stopped being magic when we built a hash table from scratch: NaiveHashTable, polynomial hashing, collisions with chaining, a 0.75 load factor and rehashing in HashTable. In practice: hashable keys, defaultdict, Counter, the tag→ids inverted index of TagSearch, memoization and two-sum. And the honest limit that opened the next module: hashing knows nothing about order and can't do ranges.

Projects contain tasks that contain subtasks: pure hierarchy. TreeNode modeled the general tree and budget showed the power of postorder (children before the parent). With BinaryNode came the tree types, the array representation (children at 2i+1/2i+2) and the four traversals, iterative versions with a stack included. The SearchTree (BST) finally answered "priority between 1 and 3" with range_query, the AVLTree guaranteed O(log n) with rotations, B/B+ trees explained database indexes, and our own Heap (sift up/sift down) rebuilt heapq from the inside for UrgentInbox 2.0. Classics: is_bst, rebuild, top_k.

"Task B can't start until A is finished" isn't hierarchy: it's a graph. The Graph class (an adjacency list as a dict of dicts, with the convention "edge A→B = B depends on A") modeled TaskFlow's DAG. BFS with deque, recursive and iterative DFS, has_cycle with white/gray/black colors and Kahn's topological_order put the work in order; connected_components grouped; dijkstra, bellman_ford and the mention of Floyd-Warshall measured paths; prim, kruskal and UnionFind wove minimum networks. The finishing touch: the complete scheduler with parallel levels and critical_path, plus suggest_collaborators, pagerank and implicit grid graphs.

This module: the seven-question method, the decision tree, the big table, and the projects ahead.

Your quick-reference index. If a name doesn't immediately bring its idea to mind, that's the lesson to review.

More important than any specific structure, because they're what you'll keep using when structures this course doesn't cover show up:

1. ADT versus implementation. A stack is a contract (push/pop/peek); list, LinkedStack or a deque are ways to fulfill it. Program against the contract and you'll be able to swap the implementation without touching the rest of the code.
2. Big O as a language. It's not decorative math: it's how you predict whether code that works with 100 elements will survive 100,000. The difference between in on a list (O(n)) and on a set (O(1)) decides whether your loop is linear or quadratic.
3. Recursion ↔ iteration. Every recursion is an implicit stack; every recursion can be rewritten with an explicit stack (and sometimes should be — remember RecursionError). Tree traversals and DFS are the same pattern in two outfits.
4. Structures that build structures. The queue on a linked list, the queue made of two stacks, the min-tracking stack, the heap on an array, the graph on a dict of dicts, the LRU cache with a dict + doubly linked list... Composing is the skill; memorizing, just the shortcut.
5. Measure instead of assuming. timeit was the course's first tool and should be the last word in any performance discussion. Theory points the way; real data decides.

An honest list: you've actually done all of this, not just read about it.

• Read and write Big O analyses of your own code, and verify the theory with timeit.
• Implement from scratch, in Python: linked lists (singly, doubly, circular), stacks, queues, ring buffers, hash tables with collisions and rehashing, BSTs, AVL trees, heaps and graphs.
• Choose among list, dict, set, deque and heapq knowing what's underneath and what each operation costs.
• Recognize patterns: LIFO → stack, FIFO → queue, "the most urgent" → heap, exact key → hash, ranges → tree, dependencies → graph.
• Apply the classic algorithms: Floyd's, tree traversals, BFS/DFS, cycle detection, topological order, Dijkstra, Bellman-Ford, Prim, Kruskal.
• Combine coordinated structures to satisfy several cost requirements at once.
• And what you don't know yet (sorting in depth, dynamic programming, tries...): you have it located, and the next lesson gives you the map to get there.

• Confusing "sounds familiar" with "I know it". The quiz below is only useful if you take it without looking; passive review produces a false sense of mastery.
• Reviewing structures as isolated flashcards. Review problems: "how would I build undo?", "how would I detect the cycle?". The structure should come to you from the problem, not the other way around.
• Skipping the whys. Knowing that dict is O(1) without remembering polynomial hashing and rehashing is fragile knowledge: it collapses at the first follow-up question in an interview.
• Not reimplementing from memory. Before the projects, try rewriting a Stack, a CircularQueue and BFS without looking. Wherever you get stuck, that's your real gap.

Self-assessment quiz. Answer without consulting the lessons, then check against the reasoned solutions.

1. In a Python list with 1,000,000 elements, which of these operations is the most expensive? (a) lst[500000] (b) lst.append(x) (c) lst.insert(0, x) (d) lst.pop()
2. The UndoRedoManager uses two stacks. When "undo" runs, what exactly happens?
3. Why does the UrgentInbox enqueue (priority, counter, task) tuples and not (priority, task)?
4. A colleague stores the ids of completed tasks in a list and checks id in completed inside a loop over 50,000 tasks. What is the total cost and how do you fix it?
5. Which structure answers "give me all the tasks with priority between 1 and 3" in O(log n + k), and why can't a dict?
6. You insert the keys 1, 2, 3, 4, 5 into a BST, in that order. What shape does the tree have, and what does it now cost to find 5? Which structure avoids this?
7. Which traversal did budget use to add up the cost of projects → tasks → subtasks, and why precisely that one?
8. In TaskFlow's dependency DAG, which algorithm gives you a valid execution order, and what signal warns you that no such order exists?
9. True or false? "A heap keeps all of its elements completely sorted."
10. Which two structures did the "review mode" cache combine (exercise 3 of the previous lesson), and what does each one contribute?

1. (c) insert(0, x) is O(n): it shifts the million elements one position over. (a) is O(1) thanks to contiguity (base + i × size); (b) and (d) are O(1) (amortized for append) because they only touch the end.
2. The undo stack is popped (the most recent action), its effect is reverted, and that action is pushed onto the redo stack. If the user then performs a new action, the redo stack is emptied: the alternative history is no longer valid.
3. Two reasons: the counter breaks ties between equal priorities, guaranteeing arrival order (FIFO within the same priority), and it also prevents heapq from trying to compare the task dicts with each other (dicts aren't comparable and it would raise TypeError).
4. in on a list is O(n); inside the loop, O(n·m) — with 50,000 tasks, on the order of billions of comparisons. You convert completed into a set once (O(m)) and each check drops to O(1): the total becomes O(n + m).
5. A BST/AVL (or a sorted list with bisect): you descend to the start of the range in O(log n) and walk the k results inorder. A dict can't because the hash function scatters on purpose: it destroys every ordering relationship between keys to achieve O(1) by exact key.
6. It degenerates into a right-leaning "list": each key is greater than the previous one, so everything hangs off the right child. Finding 5 costs O(n). The AVL avoids it: it rotates when it detects imbalance and guarantees O(log n) height no matter how the input arrives.
7. Postorder: it processes the children before the parent, so that when it's time to compute a node's budget, the budgets of all its subtrees are already computed and it's enough to add them up.
8. The topological order (Kahn: keep extracting nodes with in-degree 0). If the algorithm finishes without having processed every vertex — or if the color-based DFS finds an edge to a gray node — there is a dependency cycle and no valid order exists.
9. False. A heap only guarantees the heap property: each parent ≤ its children (in a min-heap). The minimum is at the root, but siblings have no order among themselves; that's why insert and extract are O(log n) rather than O(n) — it's a "sufficient" order, not a total one.
10. A dict id→node (locate in O(1)) and a doubly linked list holding the usage order (move a node to the head and evict from the tail in O(1)). The dict knows nothing about order; the list can't search: together, every operation is O(1).

Interpreting your score: 9-10 correct, you're ready for the projects; 6-8, review the lessons behind the questions you missed; below 6, go back to the exercises of your weak modules before continuing — the final projects assume all of this.

TaskFlow has gone from a loose dict to a system with seven families of structures working in coordination, and you have gone from using list "just because" to justifying every choice with operations and costs. The map is complete: the foundations (module 1), the linear structures (2-4), the indexes (5), the hierarchies (6), the networks (7) and the judgment (8). In the next lesson I leave you the library: the resources to keep growing on your own once this course ends.