Java § data-structures

Data structures

Java’s standard collections live in the java.util package and are organised into the Collections Framework — a coordinated suite of interfaces, abstract base classes, and concrete implementations. The principal interfaces are Collection<T>, List<T>, Set<T>, Map<K, V>, Queue<T>, and Deque<T>; the principal implementations are ArrayList, LinkedList, HashMap, TreeMap, HashSet, TreeSet, ArrayDeque, and PriorityQueue. The framework is the conventional foundation for any non-trivial Java program; familiarity with the interfaces and the choice of implementation is part of fluency in the language.

This page covers the collection types, the choice among them, the iterator and enumeration model, and the conventions for using each. The streams API — built on top of collections — is treated separately in Streams.

The Collections Framework architecture

The framework distinguishes:

Layer	Examples
Top-level interfaces	`Iterable<T>`, `Collection<T>`, `Map<K, V>`
Sub-interfaces	`List<T>`, `Set<T>`, `SortedSet<T>`, `Queue<T>`, `Deque<T>`, `SortedMap<K, V>`, `NavigableMap<K, V>`
Abstract base classes	`AbstractList`, `AbstractSet`, `AbstractMap` (rarely directly extended)
Concrete implementations	`ArrayList`, `HashMap`, `TreeSet`, `ArrayDeque`, etc.
Utility classes	`Collections`, `Arrays`

The conventional discipline:

Declare variables and parameters using the interface type (List<String>, not ArrayList<String>).
Use the most-restrictive interface that satisfies the need (a method that only iterates should accept Iterable<T>, not Collection<T>).
Choose the implementation based on the access pattern (lookup-heavy → HashMap; ordered iteration → TreeMap; etc.).

List<String>      names = new ArrayList<>();        // List interface, ArrayList impl
Map<String, Integer> ages = new HashMap<>();        // Map interface, HashMap impl
Set<Integer>      seen   = new HashSet<>();         // Set interface, HashSet impl

`List<T>`

A List<T> is an ordered sequence of elements with index-based access. The principal implementations:

Implementation	Backing	Notes
`ArrayList<T>`	dynamic array	The default; fast random access; slow middle insertion
`LinkedList<T>`	doubly-linked list	Slow random access; fast middle insertion given an iterator
`Vector<T>`	dynamic array, synchronised	Legacy; rarely used
`Stack<T>`	extends `Vector<T>`	Legacy; use `ArrayDeque`

ArrayList<T> is the conventional default:

List<String> names = new ArrayList<>();
names.add("alice");
names.add("bob");
names.addAll(List.of("carol", "dave"));

names.set(0, "Alice");                 // overwrite
names.remove(1);                        // remove by index
boolean has = names.contains("Alice");

String first = names.get(0);
int    size  = names.size();

The principal performance characteristics:

Operation	`ArrayList`	`LinkedList`
`get(i)`	O(1)	O(n)
`add(e)` (at end)	Amortised O(1)	O(1)
`add(0, e)` (at beginning)	O(n)	O(1)
`remove(i)`	O(n)	O(n), but O(1) if you have the iterator
`contains(e)`	O(n)	O(n)
`iterator().next()`	O(1)	O(1)

LinkedList<T> is rarely the right choice. Cache-unfriendliness, allocation per node, and the overhead of node references usually make ArrayList faster for typical workloads even when the asymptotic complexity favours the linked list.

Immutable lists

Java 9 introduced static factory methods for immutable lists:

List<String> empty   = List.of();
List<String> single  = List.of("alice");
List<String> several = List.of("alice", "bob", "carol");
List<String> copy    = List.copyOf(other);                 // immutable copy

The returned lists are immutable: add, remove, and set throw UnsupportedOperationException. They are the conventional contemporary form for fixed lists; older code uses Collections.unmodifiableList(new ArrayList<>(items)).

`Set<T>`

A Set<T> is a collection of unique elements. The principal implementations:

Implementation	Backing	Notes
`HashSet<T>`	hash table	The default; O(1) operations; no order
`LinkedHashSet<T>`	hash table + linked list	Insertion-order iteration
`TreeSet<T>`	red-black tree	O(log n) operations; sorted iteration

Set<Integer> primes = new HashSet<>(List.of(2, 3, 5, 7, 11));
primes.add(13);
boolean has5 = primes.contains(5);

primes.remove(11);
primes.removeAll(List.of(7));
boolean disjoint = Collections.disjoint(primes, List.of(4, 6, 8));

Set<T> admits the conventional set operations: addAll (union), retainAll (intersection), removeAll (difference). The Collections.disjoint helper tests whether two sets share elements.

The conventional choice:

HashSet<T> for general-purpose membership testing.
LinkedHashSet<T> when iteration order matters (e.g., recently-used caches).
TreeSet<T> when sorted iteration or range queries are needed.

For user-defined element types, override equals and hashCode (records do this automatically) — HashSet<T> requires both.

`Map<K, V>`

A Map<K, V> is a key-to-value association. The principal implementations:

Implementation	Backing	Notes
`HashMap<K, V>`	hash table	The default; O(1) operations
`LinkedHashMap<K, V>`	hash table + linked list	Insertion-order iteration
`TreeMap<K, V>`	red-black tree	O(log n); sorted by key
`Hashtable<K, V>`	hash table, synchronised	Legacy; rarely used

Map<String, Integer> ages = new HashMap<>();
ages.put("alice", 30);
ages.put("bob", 28);

ages.put("alice", 31);                  // overwrite
ages.putIfAbsent("carol", 35);           // insert if absent

Integer age = ages.get("alice");          // 31; null if absent
boolean has = ages.containsKey("alice");
int     size = ages.size();
ages.remove("bob");

The principal map operations:

Operation	Effect
`put(k, v)`	Insert or overwrite
`putIfAbsent(k, v)`	Insert only if `k` is absent
`get(k)`	Lookup; `null` if absent
`getOrDefault(k, default)`	Lookup with default
`remove(k)`	Remove
`containsKey(k)` / `containsValue(v)`	Membership tests
`keySet()` / `values()` / `entrySet()`	Views into the map
`size()` / `isEmpty()`	Size queries
`compute(k, fn)`	Recompute the value for `k`
`merge(k, v, fn)`	Merge into existing value
`forEach((k, v) -> ...)`	Iteration

The entrySet() is the conventional way to iterate keys and values together:

for (var entry : ages.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Atomic update patterns

Modern Map<K, V> admits several atomic-update operations:

// putIfAbsent: insert if absent
counts.putIfAbsent(key, 0);

// compute: recompute the value
counts.compute(key, (k, v) -> v == null ? 1 : v + 1);

// merge: combine with existing
counts.merge(key, 1, Integer::sum);

// computeIfAbsent: insert a default lazily
List<String> bucket = bucketsByKey.computeIfAbsent(key, k -> new ArrayList<>());
bucket.add(item);

computeIfAbsent is the conventional pattern for “insert a default and return it”; the lambda is invoked only when the key is absent.

Immutable maps

Java 9 introduced immutable maps:

Map<String, Integer> ages = Map.of(
    "alice", 30,
    "bob", 28,
    "carol", 35
);

Map<String, Integer> empty = Map.of();
Map<String, Integer> copy  = Map.copyOf(other);

// For more than 10 entries, use Map.ofEntries:
Map<String, Integer> many = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2),
    // ...
);

The returned maps are immutable; put, remove, and clear throw UnsupportedOperationException.

`Queue<T>` and `Deque<T>`

A Queue<T> is a FIFO ordering; a Deque<T> is a double-ended queue. The principal implementations:

Implementation	Notes
`ArrayDeque<T>`	The conventional choice for both queue and stack roles
`LinkedList<T>`	Implements both `Queue` and `Deque`
`PriorityQueue<T>`	A min-heap (or custom-ordered) queue
`ArrayBlockingQueue<T>`, `LinkedBlockingQueue<T>`	Concurrent variants

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);                   // add to tail
queue.offer(2);
queue.offer(3);

int first = queue.poll();         // 1; remove from head; null if empty
int peek  = queue.peek();          // 2; head; null if empty

// As a stack:
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);                    // add to head
stack.push(2);
stack.push(3);

int top = stack.pop();             // 3; remove from head

ArrayDeque<T> is the conventional choice for both queue and stack roles. LinkedList<T> works but is slower; Stack<T> is the legacy synchronised stack and should be avoided.

PriorityQueue<T> is a min-heap by default; the smallest element is at the head:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);

while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
    // 1 2 3
}

// Max-heap:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

`Iterable<T>` and `Iterator<T>`

Iterable<T> is the supertype of every collection (and of any user-defined iterable type). It declares one method:

public interface Iterable<T> {
    Iterator<T> iterator();
}

Iterator<T> provides forward traversal:

public interface Iterator<E> {
    boolean hasNext();
    E       next();
    default void remove() { throw new UnsupportedOperationException(); }
}

The enhanced for loop calls iterator() and walks through hasNext/next:

List<String> items = List.of("a", "b", "c");
for (var item : items) {
    System.out.println(item);
}

// Equivalent to:
Iterator<String> it = items.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

The full treatment is in Loops.

Fail-fast vs fail-safe iterators

The java.util collections produce fail-fast iterators: if the collection is modified during iteration (other than through the iterator’s remove), the iterator throws ConcurrentModificationException:

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
for (Integer n : list) {
    if (n == 2) list.remove(Integer.valueOf(2));    // throws ConcurrentModificationException
}

The conventional alternatives:

Use Iterator.remove():

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 2) it.remove();
}

Use Collection.removeIf:

list.removeIf(n -> n == 2);

The java.util.concurrent collections produce fail-safe iterators that operate on a snapshot of the underlying data; modifications to the collection do not affect the iteration.

`Comparable<T>` and `Comparator<T>`

Two interfaces govern ordering:

Comparable<T> — a type defines its natural ordering by implementing int compareTo(T other).
Comparator<T> — a separate object that compares two values; admits ad-hoc ordering different from the natural order.

public class Version implements Comparable<Version> {
    private final int major, minor, patch;

    @Override
    public int compareTo(Version other) {
        int dm = Integer.compare(major, other.major);
        if (dm != 0) return dm;
        int dn = Integer.compare(minor, other.minor);
        if (dn != 0) return dn;
        return Integer.compare(patch, other.patch);
    }
}

List<Version> versions = ...;
Collections.sort(versions);                         // uses compareTo

// Or with a comparator:
versions.sort(Comparator.comparing(Version::major)
                          .thenComparing(Version::minor)
                          .thenComparing(Version::patch));

// Reverse order:
versions.sort(Comparator.<Version>reverseOrder());

The Comparator static methods (comparing, comparingInt, naturalOrder, reverseOrder, nullsFirst, nullsLast) admit composing comparators concisely.

`Collections` and `Arrays` utility classes

Two utility classes provide static helpers:

Collections — operations on collections (sort, reverse, shuffle, find, frequency, unmodifiable wrappers).
Arrays — operations on arrays (sort, search, fill, asList, stream, equals, hashCode, toString).

List<Integer> list = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(list);                                         // [1, 1, 2, 3, 4, 5, 6, 9]
Collections.reverse(list);                                       // [9, 6, 5, 4, 3, 2, 1, 1]
int max = Collections.max(list);

int[] arr = { 3, 1, 4, 1, 5 };
Arrays.sort(arr);
int idx = Arrays.binarySearch(arr, 4);
List<Integer> view = Arrays.asList(1, 2, 3);                     // fixed-size list view

The Collections.unmodifiableList(list) and similar wrappers produce read-only views of mutable collections. Modern code often prefers the immutable factory methods (List.of, Map.of) instead.

Choice of collection

The conventional decision tree:

Need	Collection
Default sequence	`ArrayList<T>`
FIFO	`ArrayDeque<T>`
LIFO	`ArrayDeque<T>` (use `push`/`pop`)
Min-heap or max-heap	`PriorityQueue<T>`
Lookup by key	`HashMap<K, V>`
Lookup by key, sorted	`TreeMap<K, V>`
Lookup by key, insertion-ordered	`LinkedHashMap<K, V>`
Set membership	`HashSet<T>`
Set membership, sorted	`TreeSet<T>`
Set membership, insertion-ordered	`LinkedHashSet<T>`
Thread-safe map	`ConcurrentHashMap<K, V>` (in `java.util.concurrent`)
Snapshot-shared	An immutable `List.of`, `Map.of`, `Set.of`, or `Collections.unmodifiableX`

The default for “I need a collection” is ArrayList<T> for sequences, HashMap<K, V> for keyed lookup, HashSet<T> for membership.

Concurrent collections

The java.util.concurrent package provides thread-safe collections:

Type	Purpose
`ConcurrentHashMap<K, V>`	Thread-safe map
`ConcurrentLinkedQueue<T>`	Thread-safe queue
`ConcurrentLinkedDeque<T>`	Thread-safe deque
`CopyOnWriteArrayList<T>`	Read-mostly thread-safe list
`BlockingQueue<T>` and implementations	Producer-consumer queue

The treatment is in Concurrency. The conventional uses are producer-consumer patterns and shared caches.

Common patterns

Counting occurrences

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.merge(word, 1, Integer::sum);
}

merge is the conventional pattern; older code uses getOrDefault plus put.

Grouping

Map<String, List<Item>> byCategory = items.stream()
    .collect(Collectors.groupingBy(Item::category));

The streams API’s groupingBy collector is the conventional contemporary form. The full treatment is in Streams.

Removal during iteration

items.removeIf(Item::isExpired);

Snapshot copy

List<Integer> snapshot = new ArrayList<>(source);    // independent copy

For thread-shared collections, the snapshot copy admits iterating without holding a lock.

Multi-map (one-to-many lookup)

Java does not have a built-in MultiMap<K, V>. The conventional substitute:

Map<String, List<String>> tagsByPost = new HashMap<>();
tagsByPost.computeIfAbsent(post, p -> new ArrayList<>()).add(tag);

Third-party libraries (Apache Commons, Guava) provide explicit Multimap types.

A note on iteration order

The conventional advice on iteration order:

HashMap, HashSet — order is unspecified; do not rely on it.
LinkedHashMap, LinkedHashSet — insertion order.
TreeMap, TreeSet — sorted by key.
ArrayList, LinkedList, ArrayDeque — insertion order.

For deterministic output (logging, hashing, comparing JSON), prefer ordered collections explicitly; do not rely on the default HashMap iteration order even though some JVMs produce stable orderings under specific conditions.