Java Common Data Structures

  • Description: A note on Java's common data structures — Collection and Map hierarchies, idiomatic implementations, contracts (equals/hashCode, Comparable/Comparator), iteration patterns, and time-complexity summary
  • My Notion Note ID: K2A-C1-1
  • Created: 2018-01-02
  • Updated: 2026-05-10
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Collections Framework at a Glance

1.1 Interface Hierarchy

Java's collections live under two unrelated root interfaces — java.util.Collection and java.util.Map. Collection extends Iterable, so any Collection works in an enhanced for loop; Map does not.

Iterable
└── Collection
    ├── List              ← ordered, indexed, duplicates allowed
    ├── Set               ← unique elements
    │   └── SortedSet → NavigableSet
    └── Queue             ← FIFO-ish access at the head
        └── Deque         ← double-ended

Map                       ← key → value, separate root
├── SortedMap → NavigableMap
└── ConcurrentMap

The interface drives the API; the concrete class drives performance. Always declare variables with the interface type and pick the implementation at construction:

List<String> names = new ArrayList<>();
Map<String, Integer> ages = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();

1.2 Picking a Concrete Class

Abstract role Default Java class Alternatives
Dynamic array ArrayList<E> LinkedList<E> (rare; fast head/tail, slow random access)
Fixed-size array E[] (raw array) Arrays.asList(...) view; List.of(...) immutable
FIFO queue ArrayDeque<E> LinkedList<E>, LinkedBlockingQueue<E> (concurrent)
LIFO stack ArrayDeque<E> (use push/pop) Legacy Stack<E> (avoid)
Double-ended queue ArrayDeque<E> LinkedList<E>
Priority queue PriorityQueue<E> PriorityBlockingQueue<E> (concurrent)
Hash map HashMap<K, V> LinkedHashMap (insertion order), ConcurrentHashMap (concurrent)
Sorted map TreeMap<K, V> ConcurrentSkipListMap (concurrent)
Hash set HashSet<E> LinkedHashSet, ConcurrentHashMap.newKeySet()
Sorted set TreeSet<E> ConcurrentSkipListSet
Tree (general) No built-in. Build with nodes; use TreeMap/TreeSet for keyed cases

Rule of thumb: default to ArrayList, ArrayDeque, HashMap, HashSet. Reach for Linked* only when iteration order matters; reach for Tree* only when ordered/range queries matter; reach for Concurrent* only when multiple threads share the structure.

2. Lists

2.1 ArrayList and LinkedList

import java.util.*;

List<Integer> a = new ArrayList<>();             // amortized O(1) append, O(1) random access
List<Integer> a2 = new ArrayList<>(1024);        // pre-size to avoid reallocations
List<Integer> a3 = new ArrayList<>(List.of(1, 2, 3));

a.add(10);                                       // append
a.add(0, 5);                                     // insert at index — O(n)
a.set(0, 7);                                     // replace
int x = a.get(0);                                // random access — O(1) for ArrayList
a.remove(0);                                     // by index — O(n) shift
a.remove(Integer.valueOf(7));                    // by value (first match) — O(n)
boolean has = a.contains(10);
int size = a.size();
boolean empty = a.isEmpty();

LinkedList<E> shares the same API but is a doubly-linked list: O(1) insertion at the ends, O(n) random access, and a per-node memory overhead. In practice, ArrayDeque is faster than LinkedList for queue/stack use cases too — a LinkedList is rarely the right pick.

Pitfall — remove(int) vs. remove(Object). list.remove(0) removes by index; list.remove(Integer.valueOf(0)) removes by value. For List<Integer>, the literal list.remove(0) always picks the index overload via auto-promotion of int, even when the intent was "remove the value 0". Wrap explicitly with Integer.valueOf(...) when removing by value.

Pitfall — modifying during iteration. Adding or removing through the list while iterating with an enhanced for loop throws ConcurrentModificationException. Use Iterator.remove() or Collection.removeIf(predicate) instead — see Section 8.

2.2 Immutable and Fixed-Size Views

List<Integer> imm = List.of(1, 2, 3);            // truly immutable, Java 9+
List<Integer> fixed = Arrays.asList(1, 2, 3);    // fixed-size view backed by varargs array
List<Integer> unmod = Collections.unmodifiableList(a);  // wrapper view; underlying may still mutate
  • List.of(...) rejects nulls, throws on any mutation, and is space-efficient.
  • Arrays.asList(...) is fixed-size, not immutable: set(i, v) works, but add / remove throw UnsupportedOperationException.
  • Collections.unmodifiableList(list) is a view: mutating the original list still changes what callers see through the wrapper.

Pitfall — Arrays.asList with primitives. Arrays.asList(new int[]{1, 2, 3}) returns a List<int[]> of size 1, not a List<Integer> of size 3. Pass Integer[] or use IntStream.of(arr).boxed().toList().

3. Stacks, Queues, and Deques

3.1 Queue Interface: Throwing vs. Non-Throwing Methods

Queue<E> defines two parallel families of methods. The throwing form is a holdover from Collection; the non-throwing form is preferred for capacity-constrained queues and idiomatic queue use.

Operation Throws on failure Returns sentinel
Insert add(e) (throws IllegalStateException if full) offer(e) (returns false)
Remove head remove() (throws NoSuchElementException if empty) poll() (returns null)
Inspect head element() (throws if empty) peek() (returns null)

Deque<E> adds *First / *Last variants, plus stack-style push / pop / peek that operate on the head.

3.2 ArrayDeque as the Default Stack and Queue

import java.util.*;

// As a queue (FIFO)
Queue<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2); q.offer(3);
int head = q.poll();                             // 1
int peek = q.peek();                             // 2

// As a stack (LIFO) — push and pop operate on the head
Deque<Integer> s = new ArrayDeque<>();
s.push(1); s.push(2); s.push(3);
int top = s.pop();                               // 3

// As a deque
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); dq.addLast(2);
dq.pollFirst(); dq.pollLast();

ArrayDeque is implemented as a circular buffer over a resizable array — no per-node allocation, cache-friendly, faster than both Stack and LinkedList for stack and queue use.

Pitfall — ArrayDeque rejects null. It uses null as an internal sentinel and throws NullPointerException on add(null) / offer(null). If you need a queue that admits null, use LinkedList<E> (which also implements Queue and Deque).

3.3 Legacy: Stack and Vector

java.util.Stack<E> extends Vector<E>, which is a synchronized ArrayList-equivalent from Java 1.0. New code should use Deque<E> s = new ArrayDeque<>() and push / pop / peek. The legacy Stack exposes those same methods plus the Vector-inherited list operations, but every call pays for an unnecessary synchronized lock.

4. PriorityQueue

java.util.PriorityQueue<E> is a binary min-heap by default — the smallest element by natural ordering sits at the head. Reverse the order with a Comparator.

import java.util.*;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();          // min-heap
minHeap.offer(3); minHeap.offer(1); minHeap.offer(4);
int smallest = minHeap.peek();                                   // 1

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom element type
record Task(int priority, String name) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority)                      // smaller priority first
);
tasks.offer(new Task(2, "build"));
tasks.offer(new Task(1, "lint"));
Task next = tasks.poll();                                        // Task(1, "lint")

// Multi-key: priority asc, then name asc as a tiebreaker
PriorityQueue<Task> tieBroken = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).thenComparing(Task::name)
);
Operation Method Complexity
Push offer(e) / add(e) O(log n)
Pop head poll() / remove() O(log n)
Peek head peek() / element() O(1)
Build from collection new PriorityQueue<>(coll) O(n)
Remove arbitrary element remove(o) O(n) — scan + sift
Contains contains(o) O(n)

Pitfall — iteration order is not priority order. for (T t : pq) and pq.iterator() walk the heap array in implementation-defined order. To traverse in priority order, drain with repeated poll(), or copy and sort: pq.stream().sorted(pq.comparator()).toList().

Pitfall — not thread-safe. PriorityQueue is unsynchronized. For concurrent producers / consumers use java.util.concurrent.PriorityBlockingQueue.

Pitfall — comparator must be a total order consistent with equals. A comparator that returns 0 for two elements treats them as equal-priority; remove(o) and contains(o) still rely on equals for identity. If the natural ordering and equals disagree, remove/contains may surprise.

5. Maps

5.1 HashMap, LinkedHashMap, TreeMap

import java.util.*;

// HashMap — unordered, average O(1) lookup
Map<String, Integer> m = new HashMap<>();
m.put("alice", 30);
m.put("bob", 25);
m.put("alice", 31);                              // overwrites; size is still 2

Integer age = m.get("alice");                    // 31; null if missing
boolean has = m.containsKey("alice");
m.remove("bob");

// LinkedHashMap — preserves insertion order on iteration
Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("a", 1); ordered.put("b", 2);        // iteration yields a, b in that order

// LinkedHashMap as an LRU cache (access-order mode)
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 100;
    }
};

// TreeMap — red-black tree; keys sorted by natural ordering or comparator
NavigableMap<Integer, String> sorted = new TreeMap<>();
sorted.put(3, "c"); sorted.put(1, "a"); sorted.put(2, "b");
sorted.firstKey();                               // 1
sorted.lastKey();                                // 3
sorted.ceilingKey(2);                            // 2 (smallest ≥ 2)
sorted.higherKey(2);                             // 3 (smallest > 2)
sorted.floorKey(2);                              // 2 (largest ≤ 2)
sorted.lowerKey(2);                              // 1 (largest < 2)
sorted.subMap(1, 3);                             // [1, 3) view

HashMap allows one null key and any number of null values. TreeMap rejects null keys (the comparator would have to handle null). ConcurrentHashMap rejects both null keys and null values.

Pitfall — mutable keys. Mutating an object after using it as a HashMap key in a way that changes its hashCode() strands the entry: it's still in the table, but lookups by the now-mutated key route to a different bucket. Treat keys as immutable, or use defensive copies.

Pitfall — containsKey then get. Two lookups when one suffices. Prefer getOrDefault(k, default), or get(k) followed by a null check (when the map disallows null values), or the functional methods below.

5.2 Java 8+ Functional Methods

Map<String, Integer> counts = new HashMap<>();

// Increment-or-insert pattern
counts.merge("a", 1, Integer::sum);              // counts: {a=1}
counts.merge("a", 1, Integer::sum);              // counts: {a=2}

// Lazy initialization of expensive values
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("k", k -> new ArrayList<>()).add("v1");
groups.computeIfAbsent("k", k -> new ArrayList<>()).add("v2");
// groups: {k=[v1, v2]} — list created exactly once

// Conditional update
counts.computeIfPresent("a", (k, v) -> v + 10);  // only if "a" exists
counts.compute("b", (k, v) -> v == null ? 1 : v + 1);

// Bulk inspection
counts.forEach((k, v) -> System.out.println(k + "=" + v));
counts.replaceAll((k, v) -> v * 2);

Integer fallback = counts.getOrDefault("missing", 0);
counts.putIfAbsent("c", 0);

merge, compute, and computeIfAbsent are the idiomatic replacements for the old if (m.containsKey(k)) { ... } else { m.put(k, ...) } pattern.

5.3 Concurrent Maps

import java.util.concurrent.*;

ConcurrentHashMap<String, Integer> cm = new ConcurrentHashMap<>();
cm.put("a", 1);
cm.computeIfAbsent("b", k -> 0);                 // atomic
cm.merge("a", 1, Integer::sum);                  // atomic increment

// Sorted concurrent map
ConcurrentNavigableMap<Integer, String> csm = new ConcurrentSkipListMap<>();

ConcurrentHashMap provides lock-free reads and fine-grained locking on writes. Bulk methods like forEach and reduce accept a parallelism threshold for parallel execution. Iteration is weakly consistent: it reflects the state at some point during traversal, never throws ConcurrentModificationException, and may or may not see concurrent updates.

Collections.synchronizedMap(new HashMap<>()) is a coarse-grained alternative that wraps every method in a single lock — almost always slower than ConcurrentHashMap under contention.

6. Sets

import java.util.*;

Set<String> s = new HashSet<>();                 // unordered, average O(1)
s.add("alice"); s.add("bob");
boolean has = s.contains("alice");
s.remove("alice");

Set<String> ordered = new LinkedHashSet<>();     // insertion order
NavigableSet<Integer> sorted = new TreeSet<>();  // red-black tree

// Immutable
Set<Integer> imm = Set.of(1, 2, 3);              // duplicates throw at construction; rejects null

// Set algebra (mutates the receiver)
Set<Integer> a = new HashSet<>(Set.of(1, 2, 3));
Set<Integer> b = new HashSet<>(Set.of(2, 3, 4));
a.retainAll(b);                                  // a = {2, 3}  (intersection)
a.addAll(b);                                     // a = {2, 3, 4} (union)
a.removeAll(b);                                  // a = {} (difference)

A Set is built directly on top of the corresponding Map: HashSet uses a HashMap, TreeSet uses a TreeMap. The same contracts and pitfalls apply — most notably, elements should be effectively immutable with respect to equals/hashCode, and TreeSet rejects null.

Pitfall — Set.copyOf rejects nulls and Collectors.toSet() doesn't. When de-duplicating a stream, stream.collect(Collectors.toUnmodifiableSet()) is the immutable analogue and similarly rejects nulls; plain toSet() returns a mutable, unspecified Set and tolerates nulls only when the underlying impl does.

7. Arrays

Java arrays are reified (the element type is part of the runtime type) and covariant — String[] is a subtype of Object[]. Length is fixed at construction.

int[] a = new int[5];                            // zero-initialized
int[] b = {1, 2, 3, 4, 5};                       // array literal
int[][] grid = new int[3][4];                    // 3 × 4 int matrix; rows zero-initialized

int len = b.length;                              // field, not method
int x = b[0];
b[0] = 10;

// Utilities live on java.util.Arrays
int[] copy = Arrays.copyOf(b, b.length);
int[] slice = Arrays.copyOfRange(b, 1, 4);       // [b[1], b[2], b[3]]
Arrays.sort(b);                                  // dual-pivot quicksort for primitives, mergesort for objects
int idx = Arrays.binarySearch(b, 3);             // requires sorted input; result undefined otherwise
String s = Arrays.toString(b);                   // "[1, 2, 3, 4, 5]"
String s2 = Arrays.deepToString(grid);           // recursive for nested arrays

boolean equal = Arrays.equals(b, copy);          // element-wise; not Arrays.deepEquals
int hash = Arrays.hashCode(b);                   // element-aware; not b.hashCode()

Conversion between arrays and lists:

Integer[] boxed = {1, 2, 3};
List<Integer> list = Arrays.asList(boxed);       // fixed-size view; reflects underlying array
List<Integer> mutable = new ArrayList<>(Arrays.asList(boxed));

Integer[] back = list.toArray(new Integer[0]);   // length 0 sentinel — JIT-friendly
Object[] back2 = list.toArray();                 // always Object[]; lossy for typed lookups

Pitfall — b.toString() and b.equals(other) on arrays. Arrays inherit Object.toString and Object.equals, so b.toString() returns something like [I@1540e19d, and b.equals(c) is reference equality. Always use Arrays.toString and Arrays.equals (or Arrays.deepEquals for nested arrays).

Pitfall — array covariance. Storing a wrong-typed element compiles but throws ArrayStoreException at runtime: Object[] o = new String[1]; o[0] = 1; throws. Generic collections don't have this hole because of erasure.

Pitfall — generic array creation. new T[n] is illegal. The standard workarounds are (T[]) new Object[n] plus an @SuppressWarnings("unchecked"), or (T[]) Array.newInstance(componentType, n) when you have the Class<T>.

8. Iteration Patterns

List<Integer> v = new ArrayList<>(List.of(1, 2, 3, 4, 5));

// Enhanced for — the default for read-only or add-via-collector iteration
for (int x : v) {
    // ...
}

// Indexed — when the index matters
for (int i = 0; i < v.size(); i++) {
    // ...
}

// Iterator with safe in-place removal
Iterator<Integer> it = v.iterator();
while (it.hasNext()) {
    int x = it.next();
    if (x % 2 == 0) it.remove();                 // OK; uses iterator's modCount
}

// Predicate-based removal — Java 8, simpler than the above
v.removeIf(x -> x % 2 == 0);

// forEach with a method reference
v.forEach(System.out::println);

// Map iteration
Map<String, Integer> m = Map.of("a", 1, "b", 2);
for (Map.Entry<String, Integer> e : m.entrySet()) {
    String k = e.getKey();
    Integer val = e.getValue();
}
m.forEach((k, val) -> System.out.println(k + "=" + val));

// Stream — for transformation and aggregation
int sumOfSquares = v.stream()
    .mapToInt(x -> x * x)
    .sum();

List<Integer> doubled = v.stream()
    .map(x -> x * 2)
    .toList();                                   // Java 16+; immutable

Pitfall — ConcurrentModificationException. Most non-concurrent collections track a modification count; structural changes via the collection (not via the iterator) during iteration trigger ConcurrentModificationException on the next next(). The exception is fail-fast, not a guarantee: it may also fire from concurrent access without locks. Use Iterator.remove(), removeIf, or copy to a new list first.

Pitfall — Collectors.toList() vs. Stream.toList(). stream.toList() (Java 16+) returns an unmodifiable list. stream.collect(Collectors.toList()) returns a mutable ArrayList. Pick deliberately.

9. equals and hashCode Contract

Any class used as a HashMap key, HashSet element, or in List.contains / List.indexOf must obey the contract from java.lang.Object:

  1. Reflexive: a.equals(a) is true.
  2. Symmetric: a.equals(b) ⇔ b.equals(a).
  3. Transitive: if a.equals(b) and b.equals(c), then a.equals(c).
  4. Consistent: repeated calls return the same result while the objects don't change.
  5. Null: a.equals(null) is false.
  6. Hash agreement: if a.equals(b), then a.hashCode() == b.hashCode(). The reverse is not required.
public final class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;       // Java 16+ pattern
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Java 16+ records (preview in 14–15, standard in 16 via JEP 395) auto-generate equals, hashCode, and toString from the component list:

public record Point(int x, int y) {}

Pitfall — overriding only one of the two. Overriding equals without hashCode (or vice versa) breaks every hash-based collection. IDEs and Lombok's @EqualsAndHashCode generate both; records do too.

Pitfall — using mutable fields in equals. If a key's equals/hashCode change after insertion into a HashMap, the entry is "lost" (still in memory, unreachable by lookup). Prefer immutable keys.

Pitfall — array fields. Arrays.equals(a, b) and Arrays.hashCode(a) are not used by default. If a class has an array field and you want value semantics, call Arrays.equals / Arrays.hashCode (or Arrays.deepEquals / Arrays.deepHashCode for nested arrays) inside equals and hashCode.

10. Comparable and Comparator

Comparable<T> defines a class's natural ordering; Comparator<T> is an external ordering supplied at the call site. Both return a signed int: negative if a comes before b, positive if b comes before a, zero if they are equal under the ordering.

public final class Version implements Comparable<Version> {
    private final int major, minor, patch;
    // constructor and accessors omitted

    @Override
    public int compareTo(Version other) {
        return Comparator.comparingInt(Version::major)
            .thenComparingInt(Version::minor)
            .thenComparingInt(Version::patch)
            .compare(this, other);
    }
}

External Comparator chains:

record Person(String name, int age) {}

List<Person> people = new ArrayList<>(...);

// Single key
people.sort(Comparator.comparingInt(Person::age));

// Multi-key, mixed direction
people.sort(
    Comparator.comparing(Person::name)
        .thenComparingInt(Person::age).reversed()
);

// Null-tolerant key
people.sort(Comparator.comparing(Person::name, Comparator.nullsFirst(Comparator.naturalOrder())));

The same Comparator flows through Collections.sort, List.sort, Stream.sorted, TreeMap, TreeSet, and PriorityQueue.

Pitfall — return value, not boolean. compareTo and compare return an int, not a boolean. Returning 1, -1, or 0 is fine; do not return a.x - b.x for int keys whose magnitude can overflow — use Integer.compare(a.x, b.x) instead.

Pitfall — must be a total order consistent with equals for sorted collections. TreeMap and TreeSet decide equality via the comparator, not equals. If compare(a, b) == 0 but !a.equals(b), the tree treats them as the same key — add/put with b overwrites a. The Javadoc spells this out as "consistent with equals."

Pitfall — Comparator.comparing(...) boxes primitives. Prefer comparingInt, comparingLong, comparingDouble and thenComparingInt(...) etc. on hot paths to avoid Integer autoboxing.

11. Time Complexity Summary

The table is organized by abstract role; columns are insertion / removal / lookup at the relevant position. n is the current size; k is the number of elements touched in a bulk operation.

Class add head add tail add at index remove head remove tail remove by index get head get tail get by index contains
int[] / T[] N/A N/A N/A N/A N/A N/A O(1) O(1) O(1) O(n)
ArrayList O(n) O(1) amortized O(n) O(n) O(1) O(n) O(1) O(1) O(1) O(n)
LinkedList O(1) O(1) O(n) O(1) O(1) O(n) O(1) O(1) O(n) O(n)
ArrayDeque (queue/stack) O(1) amortized O(1) amortized N/A O(1) O(1) N/A O(1) O(1) N/A O(n)
PriorityQueue N/A O(log n) N/A O(log n) N/A O(n) by value O(1) N/A N/A O(n)
Class put / add remove get / containsKey iteration order
HashMap / HashSet O(1) avg, O(log n) worst since Java 8 O(1) avg O(1) avg none guaranteed
LinkedHashMap / LinkedHashSet O(1) avg O(1) avg O(1) avg insertion (or access-order for LinkedHashMap)
TreeMap / TreeSet O(log n) O(log n) O(log n) sorted by comparator
ConcurrentHashMap O(1) avg O(1) avg O(1) avg weakly consistent
ConcurrentSkipListMap O(log n) avg O(log n) avg O(log n) avg sorted, weakly consistent

The "O(log n) worst" cell for HashMap reflects the Java 8 change that converts a bucket into a red-black tree once it holds at least TREEIFY_THRESHOLD = 8 entries (and the table is at least MIN_TREEIFY_CAPACITY = 64). The tree is ordered primarily by hashCode; on ties, keys that implement Comparable use their compareTo for tie-breaking, which gives the O(log n) lookup guarantee. The OpenJDK source notes that performance "degrades gracefully... so long as they are also Comparable". Without Comparable, the tree falls back to System.identityHashCode tie-breaking — useful for tree shape but not semantic equality — so a worst-case bucket with all-colliding hash codes can still degrade toward O(n). The mechanism mitigates hash-flood denial-of-service most effectively against String and other Comparable keys.

12. References