Chapter VI
Data Structures in Java
A guided tour of the workhorses of the Java Collections Framework — from arrays and hash maps to tries, heaps and union-find. Each page explains the shape of the structure, its complexity, and a small runnable program you can experiment with.
Lessons
12
Reading time
290 min
Structures
11
§ 6.0122 min§ 6.0220 min§ 6.0324 min§ 6.0428 min§ 6.0526 min§ 6.0622 min§ 6.0730 min§ 6.0822 min§ 6.0928 min§ 6.1026 min§ 6.1124 min§ 6.1218 min
Arrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner
LinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner
Stacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Intermediate
HashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate
TreeMap, TreeSet, and ordered structures
Red-black trees under the hood. O(log n) sorted access, range queries, and floor/ceiling lookups.
Intermediate
PriorityQueue — heaps in disguise
Binary heaps, O(log n) insert and extract-min, and the canonical k-largest pattern.
Intermediate
Graphs — adjacency lists and BFS
Modeling graphs in plain Java with Map<Node, List<Node>>, then walking them breadth-first.
Advanced
HashSet and LinkedHashMap — uniqueness and order
Deduping in O(1), preserving insertion order, and building an LRU cache in 6 lines.
Intermediate
Binary Search Trees from scratch
Build a BST, understand insert and search, and see why balance is everything.
Advanced
Tries — prefix search and autocomplete
A tree keyed by character. Autocomplete, spellcheck, and IP routing tables all live here.
Advanced
Union-Find (Disjoint Set)
Track connected components in near-constant time with path compression and union by rank.
Advanced
Immutable and unmodifiable collections
List.of, Map.copyOf, Collections.unmodifiableList — knowing which is which prevents subtle bugs.
Intermediate
Cheatsheet
Complexity at a glance
Average-case time complexity for the operations you'll use every day. Star marks amortized cost.
| Structure | Access | Search | Insert | Remove | Notes |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1)* | O(n) | Amortized append; contiguous memory |
| LinkedList | O(n) | O(n) | O(1) | O(1) | Only at ends; ArrayDeque is usually better |
| ArrayDeque | O(1) ends | O(n) | O(1) | O(1) | Best stack & queue |
| HashMap | — | O(1) | O(1) | O(1) | Average case; needs good hashCode |
| LinkedHashMap | — | O(1) | O(1) | O(1) | Preserves insertion / access order |
| TreeMap | — | O(log n) | O(log n) | O(log n) | Sorted, range & floor/ceiling queries |
| HashSet | — | O(1) | O(1) | O(1) | Uniqueness, no order |
| TreeSet | — | O(log n) | O(log n) | O(log n) | Sorted uniqueness |
| PriorityQueue | O(1) peek | O(n) | O(log n) | O(log n) | Binary heap; smallest first by default |
| Trie | — | O(k) | O(k) | O(k) | k = key length; great for prefixes |
| Union-Find | — | O(α(n)) | O(α(n)) | — | Near-constant with path compression |
Decision guide
Pick the right structure
- You need fast random access by indexArrayList
- You push and pop from either endArrayDeque (as stack or queue)
- You need unique elements without caring about orderHashSet
- You need key → value lookup by hashHashMap
- You need keys iterated in sorted orderTreeMap / TreeSet
- You need to preserve insertion order or build LRULinkedHashMap
- You repeatedly extract the smallest/largest itemPriorityQueue
- You do prefix search or autocompleteTrie
- You track connected components / groupsUnion-Find
Practice
Test what you've learned
Take a timed exam to check your understanding of Java data structures and core language concepts.
Open Exam Center →