Collections and iterators

Why it matters

Most performance problems in application code are not exotic. They are a list searched with contains inside a loop, a linked list indexed by position, or a sorted structure used where a hash would do. Picking a collection by the operations you need, and knowing their costs, prevents a whole class of slow code. It also matters in low-level design interviews, where "which data structure holds this?" is asked about every component.

The idea

A collection is an abstract type (list, set, map, queue) plus an implementation (array, linked nodes, hash table, balanced tree, heap). The abstract type says what you can do; the implementation decides how fast each operation is. Choose the abstract type from the semantics you need, then the implementation from the operations you do most.

Array-backed versus linked

Linked lists promise O(1) insertion anywhere, but only once you have a pointer to the spot, and finding it is O(n). Every node is a separate heap object, so traversal chases pointers and misses the CPU cache constantly, as the memory hierarchy lesson explains. Dynamic arrays store elements contiguously, iterate at cache speed and grow by doubling, so appends are cheap on average. In practice an array-backed list or deque beats a linked list for almost every workload; linked structures earn their place inside other structures (LRU caches, intrusive lists) where you already hold the node.

Hash versus tree

Hash-based sets and maps give constant-time operations on average and no ordering, and they depend on correct equals and hashCode (the equality lesson). Tree-based ones cost O(log n) and give sorted iteration, range queries and nearest-key lookups. Use a hash by default; use a tree when you need order. Many languages also offer insertion-ordered hash maps (Java's LinkedHashMap, Python's dict since 3.7), which make building an LRU cache a few lines.

Iterators

An iterator walks a collection one element at a time without exposing its internals, and is what for (x : items) and for x in items use under the hood. Writing your own iterable type lets callers loop over it without knowing whether it is backed by an array, a tree or a paginated API.

Most standard collections are fail-fast: if the collection is structurally modified while you iterate (except through the iterator's own remove), the next step throws ConcurrentModificationException in Java, or behaves unpredictably elsewhere. Remove through the iterator, use removeIf, collect changes and apply them after, or build a new collection.

for (Order o : orders) if (o.isCancelled()) orders.remove(o);  // throws on the next iteration
orders.removeIf(Order::isCancelled);                            // correct and clear

Immutable and unmodifiable collections

An unmodifiable view blocks changes through that reference but reflects changes to the underlying collection; an immutable collection (List.of, Set.copyOf, Guava's immutable types, Python's tuple and frozenset) can never change. Immutable collections are safe to return from methods, share between threads and use as map keys when their elements are immutable. Return them by default from public methods, as the encapsulation lesson argues.

Concurrency

Standard collections are not thread-safe. Shared mutable collections need a lock, a concurrent implementation (ConcurrentHashMap, concurrent queues) or, better, no sharing: confine collections to one thread or share only immutable ones.

Trade-offs

Every implementation trades one operation's speed for another's: arrays favour indexing and iteration over middle insertion; hashes favour lookup over order; trees favour order over raw speed; heaps favour finding the extreme over searching. The constant factors from memory layout often matter more than the Big O, which is why array-backed structures win more benchmarks than their complexity suggests.

In an interview

Name the structure with its operation costs: "Active sessions are a hash map from token to session for O(1) lookup; expiry uses a binary heap ordered by expiry time so the next session to expire is always at the top; the LRU cache is a hash map plus a doubly linked list so both lookup and recency updates are O(1)."