Java Collections: ArrayList, HashMap, TreeMap, Immutable & Concurrent

Q: When should I use LinkedList instead of ArrayList?

Rarely. ArrayList is faster for almost all workloads, including many insertions, thanks to memory locality. For queue or deque behavior, ArrayDeque is better than LinkedList. LinkedList only helps in niche cases with iterator-based insertion and removal in the middle of large lists.

Q: What's the difference between HashMap, LinkedHashMap, and TreeMap?

HashMap offers the fastest average operations, with no ordering guarantee. LinkedHashMap adds predictable iteration order (insertion, or access order for LRU caches). TreeMap keeps keys sorted, with O(log n) operations and range queries.

Java Collections Framework

The Collections Framework is the standard library of data structures in Java: interfaces like List, Set, Map, Queue, and Deque, with implementations tuned for different access patterns. Choosing well matters: the wrong collection turns an O(1) lookup into O(n), breaks ordering guarantees, or introduces concurrency bugs.

Modern Java has refined the framework: immutable factory methods (List.of, Map.of), sequenced collections (Java 21) with uniform first and last element access, and mature concurrent collections. This page covers the core types, how the key implementations work, and practical guidance for choosing between them.

TL;DR

List: ordered, indexed, allows duplicates. Use ArrayList almost always.
Set: unique elements. HashSet (fast, unordered), LinkedHashSet (insertion order), TreeSet (sorted).
Map: key-value pairs. HashMap, LinkedHashMap (insertion or access order, LRU caches), TreeMap (sorted keys, range queries).
Queue/Deque: ArrayDeque for stacks and queues, PriorityQueue for heaps.
Prefer immutable collections (List.of, Map.copyOf) for fixed data and safe sharing.
Hash-based collections require correct equals/hashCode; use ConcurrentHashMap and friends for shared mutable state across threads.

Quick Example

Core Concepts

The Interface Hierarchy

Declare variables by interface (List<String> names = new ArrayList<>()) so implementations can change.

Performance Characteristics

See Big-O notation.

ArrayList vs LinkedList

ArrayList stores elements contiguously: fast indexed access, cache-friendly iteration, amortized O(1) appends. LinkedList stores nodes with pointers, so each element costs much more memory and gets poor cache locality. In practice ArrayList (or ArrayDeque for queue operations) wins almost every benchmark. LinkedList is rarely the right choice.

How HashMap Works

HashMap uses an array of buckets indexed by the key's hashCode() (spread and masked). Colliding keys chain within a bucket, and heavily colliding buckets convert to balanced trees (since Java 8), bounding worst-case lookups. When the size exceeds capacity × load factor (0.75), the table doubles and entries rehash. Implications:

Keys need correct, consistent equals and hashCode. Records and enums provide them.
Don't mutate keys after insertion: a changed hash code strands the entry in the wrong bucket.
Presize maps when the size is known (HashMap.newHashMap(expected), Java 19+) to avoid repeated resizing.

See hash tables.

Sorted Collections

TreeMap and TreeSet are red-black trees ordered by natural ordering or a Comparator: O(log n) operations, plus navigation (floorKey, ceilingEntry, headMap, tailMap, subMap). They're ideal for time-series lookups, leaderboards, and scheduling. Comparators must be consistent with equals, or sets may consider distinct objects duplicates.

Immutable Collections

List.of, Set.of, Map.of, Map.ofEntries: compact, unmodifiable, and they reject nulls (and duplicates for sets and map keys).
List.copyOf, and similar, create unmodifiable copies (no copy if already unmodifiable).
Collections.unmodifiableList(list) is a read-only view: changes to the underlying list show through.
Stream.toList() returns an unmodifiable list.

Immutable collections are thread-safe to share, safe to return from APIs, and prevent accidental modification. See records.

Concurrent Collections

Collections.synchronizedList wraps every method in a lock, but iteration still requires manual synchronization. Concurrent collections are usually better. See concurrency patterns.

Best Practices

Default to ArrayList, HashMap, and ArrayDeque

They cover most needs with excellent performance. Switch implementations only for specific requirements: ordering, sorting, concurrency, or memory.

Use the Map Default Methods

getOrDefault, putIfAbsent, computeIfAbsent, merge, and compute express common patterns (counters, multimaps, caches) concisely and, in ConcurrentHashMap, atomically.

Return Immutable Collections From APIs

Returning internal mutable lists lets callers corrupt object state. Return List.copyOf(items) or unmodifiable views, and document it.

Use EnumSet and EnumMap for Enum Keys

They're backed by bit vectors and arrays, so they're extremely fast and compact compared to hash-based alternatives.

Common Mistakes

Modifying a Collection While Iterating

Mutable Keys in HashMap or HashSet

Changing a field used by hashCode after insertion makes the element unfindable, and it can't be removed. Use immutable keys: records, strings, and IDs.

Calling contains on Large Lists Repeatedly

list.contains(x) inside a loop is O(n²). Convert to a HashSet first for O(1) lookups.

FAQ

When should I use LinkedList instead of ArrayList?

Rarely. ArrayList is faster for almost all workloads, including many insertions, thanks to memory locality. For queue or deque behavior, ArrayDeque is better than LinkedList. LinkedList only helps in niche cases with iterator-based insertion and removal in the middle of large lists.

What's the difference between HashMap, LinkedHashMap, and TreeMap?

HashMap offers the fastest average operations, with no ordering guarantee. LinkedHashMap adds predictable iteration order (insertion, or access order for LRU caches). TreeMap keeps keys sorted, with O(log n) operations and range queries.

Are List.of lists immutable?

Yes. They're unmodifiable, and attempts to add, remove, or set elements throw UnsupportedOperationException. They also disallow null elements. Their contained objects can still be mutable, though.

Is HashMap thread-safe?

No. Concurrent modification can corrupt it or lose updates. Use ConcurrentHashMap for shared mutable maps, or confine maps to a single thread, or use immutable maps for shared read-only data.