Choosing the right data structure often matters more than the algorithm itself. The method is simple: find the dominant operation, check the limits, take the simplest built-in type and verify the choice by counting operations. The previous lesson gave the ADT catalog; this lesson turns it into a decision rule.
Choosing by the dominant operation
Break the task into operations: search, insert, delete, order, min/max, a range query. The choice is decided by the most frequent operation on the largest n. Then look at the limits: memory, duplicates, whether keys are hashable, whether order matters. The costs of the main structures:
| Structure | Find | Insert | Min / order |
|---|---|---|---|
list | O(n) | end O(1), middle O(n) | O(n) |
| sorted list | O(log n) | O(n) | O(1) |
deque | O(n) | both ends O(1) | O(n) |
set / dict | O(1) average | O(1) average | O(n) |
heapq | O(n) | O(log n) | O(1) |
