What's changed: Initial version
1.3Data structures
Covers the time complexity of basic operations on arrays, lists, stacks, and queues; tree structures (binary search trees, balanced trees, heaps) for hierarchical data; hashing for direct key-to-location lookup; and graphs for relational data—each paired with its time-complexity characteristics.
FE already covers basic data structures, but at AP level you are expected to explain why a given time complexity arises from the structure itself. Why must a tree stay balanced? Why do hash collisions degrade performance? Understanding this causal link between structure and complexity is the foundation for the algorithm design covered in the next section.
1.3.1Arrays, lists, stacks, and queues
- An array lays out elements in contiguous memory, giving O(1) indexed access, but insertion/deletion in the middle requires shifting elements, costing O(n). A list (linked list) gives O(1) insertion/deletion in the middle via reference rewiring, but accessing the n-th element requires walking from the head, costing O(n).
- Both stacks (LIFO) and queues (FIFO) are specialized lists whose push/pop or enqueue/dequeue operations run in O(1). Choose by use case: a call stack or bracket-matching check uses a stack; breadth-first search or a job queue uses a queue.
1.3.2Tree structures (BST, balanced trees, heaps)
- A binary search tree (BST) satisfies, at every node, "all left-subtree elements < the node < all right-subtree elements." Search, insert, and delete are proportional to the tree's height—O(log n) on average—but a skewed insertion order can degenerate into a linear chain (a skewed tree), worsening to O(n) in the worst case.
- A balanced tree (AVL tree, red-black tree, etc.) is an enhanced BST that automatically corrects height imbalance on every insert/delete, always guaranteeing O(log n). Not degrading even in the worst case is why it is chosen in practice.
- A heap is a complete binary tree satisfying the heap property: every parent is greater than (or less than) its children. Retrieving the max (or min) is always O(1) (just look at the root), and insert/delete are proportional to the tree's height at O(log n). Heaps implement priority queues.
Most-tested contrasts: "array = O(1) access, O(n) insertion", "list = O(n) access, O(1) insertion", "BST = O(log n) on average but O(n) worst case when skewed", "balanced tree = always guarantees O(log n)", and "heap = O(1) to retrieve the max/min". Be able to explain why each complexity arises from tree height or the contiguous-memory structure.
1.3.3Hashing and graphs
- Hashing converts a key into a fixed-length hash value via a hash function and uses it as an array index, achieving O(1) on average for search and insertion. When different keys map to the same hash value—a collision—it is handled with techniques such as chaining (storing multiple entries as a linked list at the same slot), but frequent collisions push performance toward O(n).
- A graph represents relationships between elements using vertices (nodes) and edges. It is well suited to expressing many-to-many relationships such as social-network friendships, road networks, and dependency management; a tree is the special case of a graph with no cycles and exactly one parent per node.
Suppose an EC site's product search needs to fetch one of a million products instantly by its product code (key). A binary search tree needs on average log2(1,000,000) ≈ 20 comparisons, but a hash table reaches the target product in about one access on average, as long as collisions stay low. If the hash function is poorly designed and many product codes cluster into the same hash value, a long chain forms at that slot and performance degrades toward O(n)—so how evenly the hash function distributes keys matters greatly. On the other hand, managing many-to-many relationships such as "related products" or "products in the same category" suits a graph: represent products as vertices and relationships as edges, and a query like "related products reachable within two hops" can be solved efficiently with breadth-first search (using a queue). Further, a requirement to always process the most-urgent, low-stock popular item first (e.g., prioritizing an inventory-check batch) suits a heap, whose root always holds the highest-priority item, giving O(log n) insertion while retrieving the top-priority item in O(1). Even for the same broad task of "handling many pieces of data," the optimal structure varies greatly depending on the access pattern—direct lookup by key, traversal of relationships, or priority-ordered retrieval.
| Structure | Search | Insert | Characteristic |
|---|---|---|---|
| Array | O(1) (indexed) | O(n) | Contiguous memory |
| List | O(n) | O(1) (if position known) | Linked via references |
| BST (average) | O(log n) | O(log n) | Worst case O(n) if skewed |
| Balanced tree | Guaranteed O(log n) | Guaranteed O(log n) | Always self-balances |
| Hash (average) | O(1) | O(1) | Degrades to O(n) with heavy collisions |
| Heap | Max/min O(1) | O(log n) | Used for priority queues |
Trap: "A binary search tree always searches in O(log n)" is wrong—depending on insertion order it can become a skewed tree (effectively a linked list), degrading to O(n) in the worst case. Use a balanced tree if you need a guaranteed O(log n). Also wrong: "a hash table is always faster than an array as long as there are no collisions"—the cost of computing the hash function and any collision-handling overhead must be considered, and for a very small number of elements, linear search on an array can be sufficient.
1.3.4Section summary
- Understand the trade-off: arrays give fast access but slow insertion, lists give fast insertion but slow access
- BST is O(log n) on average but O(n) worst case if skewed; balanced trees always guarantee O(log n); heaps retrieve the max/min in O(1)
- Hashing is O(1) on average but degrades with more collisions; graphs express many-to-many relationships
Sign in to track progress — Log in.
Quick check
(just a quick review)Q1. Which statement about binary search trees is most appropriate?
Q2. You want to retrieve the highest-priority task in O(1) at all times while adding new tasks in O(log n). Which data structure is most appropriate?
Q3. For frequently looking up one of one million product records by its product-code key, prioritizing average-case performance, which structure is most appropriate?