Data Structures Foundation
mediumDataStructuresBigOAlgorithmsMemoryModel
Understanding Java collections requires a deep dive into the primary data structures that power them. Every collection is an engineering trade-off between Time Complexity ($O(n)$) and Space Complexity.
1. Core Data Structures Comparison
| Structure | Big-O (Access) | Big-O (Search) | Memory Layout | Java Implementation |
|---|---|---|---|---|
| Array | $O(1)$ | $O(n)$ | Contiguous | ArrayList, ArrayDeque |
| Linked List | $O(n)$ | $O(n)$ | Discrete | LinkedList |
| Hash Table | N/A | $O(1)$ | Array + List/Tree | HashMap, HashSet |
| B-Tree / Red-Black | $O(\log n)$ | $O(\log n)$ | Tree nodes | TreeMap, TreeSet |
| Heap | $O(1)$ (peek) | $O(n)$ | Complete Tree | PriorityQueue |
2. Architectural Analysis
2.1 Arrays vs. Linked Lists (Spatial Locality)
The primary performance difference between ArrayList and LinkedList is not just Big-O, but CPU Cache Locality.
- Arrays are stored in contiguous memory blocks. The CPU pre-fetcher can load 64-byte chunks (Cache Lines) into L1 cache, making sequential access 10-50x faster.
- Linked Lists scatter nodes across the heap. Accessing the next element involves "pointer chasing," which almost always results in a Cache Miss, forcing the CPU to wait for slow RAM.
2.2 Rebalancing: The Red-Black Tree
Java's TreeMap and the collision strategy of HashMap (when a bucket exceeds 8 elements) use Red-Black Trees.
- Constraint: The longest path is no more than twice the shortest path.
- Trade-off: Slightly less balanced than AVL trees, but much faster at Insert/Delete operations due to fewer rotations.
3. The Power of 2 (Hashing)
Java's HashMap always uses a capacity of $2^n$ (16, 32, 64...). This is a critical optimization:
- Standard Modulo:
hash % length(Slow). - Bitwise Masking:
hash & (length - 1)(Ultra-fast). This bitwise operation is only equivalent to modulo when the length is a power of 2.