Data Structures & Big-O (CS 201) · Module 3 of 9
Arrays, Linked Lists & Amortized Analysis
The two foundational linear structures, and the accounting trick that explains why dynamic arrays feel like O(1).
Static vs. Dynamic Arrays
- A static array has a fixed size; a dynamic array (like Python's list or Java's ArrayList) automatically resizes by allocating a new, larger array and copying elements when it runs out of space.
- Dynamic arrays typically double in size when they need to grow, which balances the cost of resizing against the cost of leaving too much unused space.
Why do dynamic arrays typically double in size rather than growing by a fixed amount, like adding 10 slots, each time they're full?
Solution. Doubling ensures that resizing happens exponentially less often as the array grows, keeping the amortized cost of each insertion low (O(1)); growing by a fixed amount would require resizing, and copying all elements, much more frequently as the array gets larger, leading to worse overall performance.
Amortized Analysis
- Amortized analysis averages the cost of an operation over a sequence of operations, showing that even though some individual operations are expensive, the average cost per operation remains low.
- For dynamic array doubling, even though occasional resizes cost O(n), the amortized cost per insertion averages out to O(1).
If inserting into a dynamic array occasionally costs O(n) due to resizing, why is the amortized cost per insertion still considered O(1)?
Solution. Resizing, which costs O(n), happens only when the array is full, and doubling means resizes become exponentially rarer as the array grows; when averaged over all insertions since the last resize, the total copying cost divided by the number of insertions works out to a constant O(1) per insertion.
Linked List Operations
- A singly linked list has O(1) insertion/deletion at the head but O(n) access to an arbitrary element, since you must traverse from the head.
- A doubly linked list adds a "previous" pointer, enabling O(1) deletion of a given node without needing to find its predecessor, and traversal in both directions.
Why is deleting a given node O(1) in a doubly linked list but potentially O(n) in a singly linked list?
Solution. In a doubly linked list, the node's "previous" pointer directly gives access to the preceding node needed to update its "next" pointer; in a singly linked list, you'd need to traverse from the head to find that preceding node, which takes O(n) time.
Arrays vs. Linked Lists: Trade-offs
- Arrays offer O(1) random access by index but O(n) insertion/deletion in the middle, since elements must shift; linked lists offer O(1) insertion/deletion once you have a reference to the location, but O(n) access to an arbitrary element.
- Arrays have better cache locality, since elements are stored contiguously in memory, often making them faster in practice despite similar theoretical complexity for some operations.
Why might an array outperform a linked list in practice, even for operations where both have the same theoretical time complexity?
Solution. Arrays store elements contiguously in memory, giving better cache locality (nearby elements are likely already loaded into fast CPU cache), while linked list nodes can be scattered throughout memory, causing more cache misses and slower actual performance despite similar Big-O complexity.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. Why do dynamic arrays typically double in size when they need to grow?
2. What does amortized analysis measure?