Given a workload, how do you use Big-O complexity to choose between ArrayList, LinkedList, HashMap, and TreeMap?
answer
- Pick by the dominant operation, then read the table
- Index/iterate → ArrayList; key lookup → HashMap
- Sorted/range → TreeMap; end queue → ArrayDeque
- Big-O ignores cache locality + memory — ArrayList usually wins ties
- Check equals/hashCode and Comparable constraints
basics
~20 sMatch the structure to the operations you do most. Index access or iteration → ArrayList. Key lookups, order not needed → HashMap. Sorted keys or range queries → TreeMap. End-only queue ops → ArrayDeque (rarely LinkedList).
solid answer
~50 sStart from the dominant operation in the workload, then read it off the complexity table. Random index access and fast iteration favour ArrayList (O(1) get, cache-friendly). Frequent key→value lookups with no ordering need favour HashMap (average O(1)). Needing sorted iteration, range scans, or nearest-key queries favours TreeMap (O(log n) but ordered). Pure end-based queue/stack usage favours ArrayDeque; LinkedList mainly if you truly need a doubly-linked deque, constant-time front insertion into a List, or edits at a positioned iterator. Crucially, do not stop at Big-O: constant factors and cache locality mean ArrayList usually beats LinkedList in practice on shared O(n) operations, and HashMap's average O(1) usually beats TreeMap's O(log n) when ordering is irrelevant. Also weigh memory (node overhead), the equals/hashCode contract for hashed structures, and whether a worst-case guarantee (TreeMap's log n) matters for an SLA.
go deeper
Can map a few common cases (index access → ArrayList, key lookup → HashMap) to the right collection.
Reads complexity off the table for the dominant operation and justifies HashMap-vs-TreeMap by the ordering requirement.
Weighs constant factors, cache locality, memory, and average-vs-guaranteed bounds, and reaches for ArrayDeque/LinkedHashMap/ConcurrentHashMap when warranted.
Drives the choice from measured workload profiles and SLA guarantees, considers concurrency and GC/memory pressure at scale, and knows when an in-memory collection should be replaced by an index/external store.
## The decision is workload-driven There is no 'fastest collection' in the abstract — the right choice depends on **which operations dominate your workload**. The method: list the operations you perform most, look up each structure's complexity for those operations, then adjust for real-world factors (cache locality, memory, ordering, contracts). ## A quick complexity reference **ArrayList** (resizable array): - get/set by index: **O(1)** - add at end: **amortized O(1)** (rare resize copy is O(n)) - add/remove in middle or front: **O(n)** (shift elements) - contains/indexOf: **O(n)** - iteration: **O(n)**, very cache-friendly **LinkedList** (doubly-linked list): - get/set by index: **O(n)** (walk the chain) - add/remove at ends: **O(1)** - add/remove at a held iterator position: **O(1)** (but finding it is O(n)) - contains: **O(n)**, poor cache locality **HashMap** (hash table): - get/put/remove/containsKey: **average O(1)**; in a collision-heavy bin O(log n) when keys have distinct hashes or are `Comparable`, otherwise O(n); a `put` that triggers a resize is also O(n) - containsValue: **O(n)** - iteration order: **unspecified** **TreeMap** (balanced BST): - get/put/remove/containsKey: **O(log n)** - first/last/ceiling/floor/range views: **O(log n)** - iteration: **O(n)**, **sorted** ## Step 1 — name the dominant operation - Mostly reading by position, or scanning all elements? → **ArrayList**. - Mostly looking values up by a key? → a **Map**. If order does not matter, **HashMap**; if you need sorted/range access, **TreeMap**. - Mostly adding/removing at the ends (queue or stack)? → **ArrayDeque** (array-backed, no per-node object); fall back to **LinkedList** for a genuine doubly-linked deque, constant-time *List* front insertion, or edits at a positioned iterator. ## Step 2 — look past Big-O Big-O describes growth, but ignores **constant factors** and **memory behaviour**: - **Cache locality:** ArrayList's references sit in one contiguous array, so neighbouring slots share cache lines; LinkedList adds a node object per element, and each hop can miss the cache. So even where both are O(n) (iteration, contains), ArrayList is usually much faster in practice. - **Memory overhead:** each LinkedList node and each Map entry is a separate heap object with pointers — significant overhead versus a packed array. - **Average vs guaranteed:** HashMap is O(1) *on average* but can spike; TreeMap is O(log n) *always*. For latency-sensitive SLAs the predictable bound can matter. ## Step 3 — check the constraints - Hashed structures (HashMap/HashSet) require correct, stable **equals/hashCode** on keys; mutable keys break them. - TreeMap/TreeSet require keys to be **Comparable** or a supplied **Comparator**; otherwise put throws `ClassCastException`. - Need predictable iteration order with hash speed? **LinkedHashMap** (average O(1), insertion or access order). - Concurrency? **ConcurrentHashMap** rather than synchronizing a HashMap. ## Worked examples - *Render a list of search results, accessed by index, iterated often* → ArrayList. - *Cache user objects by id, order irrelevant* → HashMap. - *Leaderboard you must show in score order and query ranges of* → TreeMap, keyed by score plus a tie-breaker, because an equal key overwrites. - *Single-threaded work queue* → ArrayDeque (as a Queue). *Producer/consumer across threads* → a `BlockingQueue` such as `ArrayBlockingQueue`, because ArrayDeque is not thread-safe. - *Deduplicate items, no order needed* → HashSet; *deduplicate and keep sorted* → TreeSet. ## The senior takeaway Default to ArrayList and HashMap; deviate only when the workload's dominant operation or an ordering/guarantee requirement justifies it, and validate with profiling rather than Big-O alone.
- Two structures are both O(n) for your scan-heavy workload — how do you choose?Look past Big-O to constant factors and cache locality. ArrayList's contiguous reference array usually iterates much faster than LinkedList's chain of nodes, and uses less memory, so pick ArrayList. Confirm with profiling on representative data.
- Why prefer ArrayDeque over LinkedList for a queue even though both offer O(1) end operations?ArrayDeque is backed by a circular array — no per-element node objects, better cache locality, and lower memory overhead — so it is likely to be faster for the same Big-O, and it forbids null which catches bugs.
- Choosing a structure from Big-O alone, ignoring cache/memory constants
- Recommending LinkedList as a general-purpose list 'because inserts are O(1)'
- Using TreeMap when no ordering is required (paying O(log n) for nothing)
- Forgetting hashed/sorted key contracts when picking a Map
- ArrayDeque
- Java 1.6
context
- HashMap (Java SE 27 & JDK 27)docs.oracle.com
- TreeMap (Java SE 27 & JDK 27)docs.oracle.com
- ArrayDeque (Java SE 27 & JDK 27)docs.oracle.com