Java Collections

Non-concurrent collection classes from java.util.

At a Glance

• ArrayList — Resizable array. O(1) random access, O(1) amortized append. Default choice for most list needs. Inserts/removes in the middle are O(n) due to shifting.
• LinkedList — Doubly-linked list that also implements Deque. O(1) insert/remove at ends or via iterator, but O(n) random access. Rarely better than ArrayList in practice due to cache locality.
• HashSet — Unordered set backed by HashMap. O(1) add/remove/contains. Default choice for sets. No ordering guarantees.
• LinkedHashSet — HashSet that maintains insertion order. Slightly more memory than HashSet. Use when you need deterministic iteration order.
• TreeSet — Sorted set backed by a red-black tree. O(log n) operations. Use when you need elements in sorted order or range queries (headSet, tailSet). No nulls.
• EnumSet — Specialized set for enum types, backed by a bit vector. Extremely fast and compact. Always prefer over HashSet when keys are enums.
• HashMap — Unordered key-value map. O(1) get/put. Default choice for maps. Allows one null key. Buckets convert to tree bins at threshold 8 for worst-case O(log n).
• LinkedHashMap — HashMap with insertion-order (or access-order) iteration. Use for predictable iteration or LRU caches via removeEldestEntry.
• TreeMap — Sorted map backed by a red-black tree. O(log n) operations. Use when you need sorted keys or range views (subMap, headMap). No null keys.
• EnumMap — Map with enum keys, backed by a plain array. Very fast and compact. Always prefer over HashMap when keys are enums.
• IdentityHashMap — Uses == instead of equals() for key comparison. Rare — useful for topology-preserving object graph operations like serialization.
• WeakHashMap — Entries are garbage-collected when keys have no strong references. Use for memory-sensitive caches. Not thread-safe.
• ArrayDeque — Resizable-array double-ended queue. O(1) amortized push/pop at both ends. Preferred over Stack and LinkedList for stack and queue use.
• PriorityQueue — Min-heap. O(log n) insert/remove, O(1) peek. Use for priority-based processing. Not thread-safe — use PriorityBlockingQueue for concurrency.

List

Ordered, index-accessible sequences. Duplicates allowed.

List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.get(0);           // "Alice"
names.set(1, "Charlie");
names.remove(0);        // removes "Alice"

// Immutable (Java 9+)
List<String> fixed = List.of("a", "b", "c");

// Immutable copy (Java 10+)
List<String> copy = List.copyOf(names);

Set

Unique elements. No duplicate values.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("collections");
tags.add("java");       // ignored — already present
tags.contains("java");  // true
tags.size();             // 2

// Immutable (Java 9+)
Set<String> fixed = Set.of("a", "b", "c");

// From enum
EnumSet<DayOfWeek> weekend = EnumSet.of(SATURDAY, SUNDAY);

Map

Key-value pairs. Keys are unique.

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.get("Alice");                     // 95
scores.getOrDefault("Eve", 0);           // 0
scores.putIfAbsent("Bob", 100);          // no-op, key exists
scores.computeIfAbsent("Eve", k -> 42); // adds Eve=42

// Iteration
scores.forEach((k, v) -> System.out.println(k + ": " + v));

// Immutable (Java 9+)
Map<String, Integer> fixed = Map.of("a", 1, "b", 2);

// LRU cache via LinkedHashMap
Map<K, V> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K, V> e) {
        return size() > MAX_SIZE;
    }
};

Queue & Deque

FIFO queues and double-ended queues.

// Stack (LIFO) — use ArrayDeque, not java.util.Stack
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
stack.pop();   // "second"
stack.peek();  // "first"

// Queue (FIFO)
Queue<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
queue.poll();  // "first"

// Priority queue (min-heap)
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.poll();  // 10 — smallest first

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

Legacy Collections

Synchronized-by-default classes from Java 1.0/1.2. Avoid in new code.

Interface Hierarchy

Iterable
 └── Collection
      ├── List       → ArrayList, LinkedList
      ├── Set        → HashSet, LinkedHashSet, TreeSet, EnumSet
      │    └── SortedSet → NavigableSet → TreeSet
      └── Queue      → PriorityQueue, ArrayDeque
           └── Deque → ArrayDeque

Map (separate hierarchy)
 ├── HashMap, LinkedHashMap, WeakHashMap, IdentityHashMap, EnumMap
 └── SortedMap → NavigableMap → TreeMap

Unmodifiable & Factory Methods