Java Collections Framework: Lists, Sets, Maps, and Queues Guide

The Java Collections Framework (JCF) is a unified architecture for storing, retrieving, and manipulating groups of objects. It provides interfaces (List, Set, Map, Queue, Deque), implementation classes, and algorithms for sorting, searching, and synchronization. Understanding the JCF is essential for writing efficient, idiomatic Java code. This guide covers every major collection type, its performance characteristics, and practical usage patterns.

The Collection Hierarchy

The JCF is rooted in the java.util package. The core interfaces form a type hierarchy described in the Oracle Java Documentation:

• Collection<E> — the root interface for List, Set, and Queue
• List<E> — ordered, indexed, allows duplicates
• Set<E> — no duplicates, no defined order (but SortedSet/NavigableSet add ordering)
• Queue<E> — FIFO or priority-ordered for processing
• Deque<E> — double-ended queue (stack + queue)
• Map<K,V> — key-value pairs (not a Collection, but part of the framework)

Each interface has multiple implementations with distinct performance tradeoffs. Choosing the right implementation is the most important decision when using the JCF.

List Implementations

ArrayList and LinkedList are the primary List implementations, plus Vector (legacy, synchronized).

ArrayList

ArrayList is a resizable array implementation. It offers O(1) random access and O(n) insertion/removal at arbitrary positions (Baeldung, “Guide to the ArrayList”). It is the most commonly used List implementation.

List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
String first = names.get(0);       // O(1)
names.remove(0);                    // O(n) — shift elements

The default capacity is 10. When exceeded, the array grows by 50%. Pre-sizing with new ArrayList<>(expectedSize) avoids reallocation overhead.

LinkedList

LinkedList implements both List and Deque. It offers O(1) insertion/removal at either end but O(n) random access. Use it when you need frequent add/remove at the beginning or middle, or when you need a queue/stack.

Deque<String> stack = new LinkedList<>();
stack.push("first");
stack.push("second");
String top = stack.pop();  // "second"

Joshua Bloch, who co-designed the JCF, notes in Effective Java (Item 65) that ArrayList outperforms LinkedList in virtually all real-world scenarios except as a Deque.

Set Implementations

HashSet, LinkedHashSet, and TreeSet cover almost all use cases.

HashSet

Backed by a HashMap, HashSet offers O(1) add, remove, and contains operations. Elements must implement hashCode() and equals() correctly — a common source of bugs (Bloch, Item 11).

Set<String> uniqueNames = new HashSet<>();
uniqueNames.add("Alice");
uniqueNames.add("Bob");
uniqueNames.add("Alice");           // ignored
boolean exists = uniqueNames.contains("Alice");  // true

LinkedHashSet

Extends HashSet with a linked list running through entries, maintaining insertion order. Useful when iteration order matters but hash-based performance is desired.

TreeSet

Implements SortedSet and NavigableSet via a red-black tree. Elements are sorted according to their natural ordering (Comparable) or a Comparator. Operations are O(log n). Use for sorted views and range queries:

TreeSet<Integer> sorted = new TreeSet<>();
sorted.add(5); sorted.add(1); sorted.add(10);
sorted.first();          // 1
sorted.headSet(6);       // [1, 5]
sorted.subSet(2, 8);     // [5]

Map Implementations

Maps store key-value associations. HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap are the essential implementations.

HashMap

The workhorse of the JCF. HashMap offers O(1) average get/put, using the key’s hashCode() to determine the bucket. From Java 8 onward, buckets with many collisions convert from linked lists to balanced trees (O(log n)) for improved performance (JEP 180).

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
int aliceScore = scores.getOrDefault("Alice", 0);  // 95

Initial capacity and load factor affect performance. The default load factor of 0.75 balances time and space. Pre-size the map when the approximate entry count is known.

LinkedHashMap

Extends HashMap with a doubly linked list maintaining insertion order (or access order for LRU caches). Override removeEldestEntry to build an LRU cache:

LinkedHashMap<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100;
    }
---;

TreeMap

A red-black tree implementation. Entries are sorted by keys. Use for range queries (subMap, headMap, tailMap) or when keys must be traversed in order.

ConcurrentHashMap

Thread-safe without locking the entire map. From Java 8, uses CAS operations and fine-grained locking. Prefer it over Collections.synchronizedMap() for concurrent access.

ConcurrentHashMap<String, Long> counters = new ConcurrentHashMap<>();
counters.merge("hits", 1L, Long::sum);  // atomic increment

Queue and Deque

PriorityQueue implements a min-heap (or max-heap with a Comparator). ArrayDeque is the recommended implementation for Deque — it outperforms LinkedList and Stack.

Queue<Task> priorityQueue = new PriorityQueue<>(Comparator.comparing(Task::priority));
priorityQueue.offer(new Task("critical", 1));
priorityQueue.offer(new Task("low", 5));
Task next = priorityQueue.poll();  // highest priority first

Sorting and Searching

The Collections utility class provides static methods for operating on collections:

• Collections.sort(List) — sorts a list (TimSort, O(n log n))
• Collections.binarySearch(List, key) — O(log n) search
• Collections.reverse(List) — reverse order
• Collections.shuffle(List) — randomize order
• Collections.unmodifiableList(List) — immutable view
• Collections.synchronizedList(List) — synchronized wrapper (prefer concurrent collections)

Integration with Streams

All Collection implementations support the Streams API (Java 8+), enabling declarative data processing:

List<String> result = names.stream()
    .filter(name -> name.startsWith("A"))
    .sorted()
    .collect(Collectors.toList());

See our Java Streams API guide for comprehensive coverage.

Choosing the Right Collection

The following decision guide (adapted from Oracle’s Collections Tutorial) helps select the correct implementation based on access patterns:

Performance Characteristics Summary

Understanding the time complexity of common operations helps avoid performance surprises:

• ArrayList: O(1) get, O(n) add at index, O(n) remove. Best for iteration and random access.
• LinkedList: O(n) get, O(1) add/remove at ends. Worst for indexed access.
• HashSet/HashMap: O(1) average for basic operations. O(n) worst-case with poor hash distribution.
• TreeSet/TreeMap: O(log n) for all operations. Guaranteed performance but higher constants.
• ConcurrentHashMap: O(1) average. Higher constant than HashMap but scales with threads.
• PriorityQueue: O(log n) for offer/poll. O(1) for peek. Unsorted internal structure.

Memory overhead also varies. ArrayList stores an Object[] array with 50% slack capacity on resizing. LinkedList allocates a node object per element (24+ bytes overhead). HashMap has internal bucket array plus entry objects. For memory-constrained environments, ArrayList and HashMap with proper initial capacity are most efficient.

FAQ

Q: When should I use ArrayList vs LinkedList? A: Use ArrayList for indexed access and iteration. Use LinkedList only when you need frequent insertion/removal at both ends (as a Deque). In most cases, ArrayList wins.

Q: Why does HashSet not guarantee insertion order? A: HashSet calculates bucket positions from hash codes. Use LinkedHashSet for predictable iteration order.

Q: What happens if I mutate a HashMap key after insertion? A: If the key’s hashCode() changes, the entry becomes unreachable via get(), causing a memory leak. Always use immutable keys (String, Integer, records).

Q: How do I make a collection thread-safe? A: Prefer ConcurrentHashMap, CopyOnWriteArrayList, or ConcurrentLinkedQueue. Avoid Collections.synchronized*() wrappers for new code — they lock the entire collection, hurting throughput.

Q: What is the difference between Collection and Collections? A: Collection is the root interface. Collections is a utility class with static helper methods.

Java 16+ introduced Stream.toList() which returns an unmodifiable list — prefer it over collect(Collectors.toList()) when mutability is not required. Java 21 adds sequenced collections (SequencedCollection, SequencedSet, SequencedMap) with reversed(), addFirst(), and getLast() methods for unified ordered collection access.

Immutable collections (List.of(), Set.of(), Map.of()) were introduced in Java 9 and are preferred when collection contents are known at creation time. They reject null elements, are space-efficient, and guarantee thread safety without synchronization. Map.copyOf() and List.copyOf() (Java 10+) create immutable copies from any source collection — use these before returning internal data structures to prevent caller mutation.

The EnumSet and EnumMap specialized collections are optimized for enum keys. EnumSet uses a bit vector internally — all operations execute in constant time with single-bit mask operations. EnumMap uses a typed array indexed by the enum’s ordinal. Both outperform their general-purpose counterparts (HashSet, HashMap) by a significant margin when working with enum types.

When choosing between collection types, always start with the simplest option — ArrayList for sequences, HashMap for associations, HashSet for uniqueness — and only introduce specialized implementations when profiling identifies a bottleneck. Premature optimization of collection selection adds complexity without measurable benefit.

The JCF is one of the most well-designed collection libraries in any programming language. Its consistent interface hierarchy, algorithm reuse through the Collections utility class, and smooth integration with the Streams API make it a model for API design.

Mastering the Collections Framework is a prerequisite for effective Java programming. Combine it with the Java Streams API for modern data processing pipelines, and refer to the Oracle Collections Tutorial for advanced patterns.

For a comprehensive overview, read our article on Java 17 21 Features.