Java Collections Framework: Choosing Between List, Set, Map, and Queue

The Collections Framework is the part of Java you’ll touch in literally every program. It’s also weirdly intimidating at first: dozens of classes with overlapping names, and tutorials that catalog all of them without ever answering the actual question — which one do I use?

Here’s the honest secret: four implementations cover about 90% of real code — ArrayList, HashMap, HashSet, and ArrayDeque. The rest exist for specific, nameable reasons. This guide gives you the map, the selection rules, and the complexity facts that make the choice mechanical.

The Shape of the Framework

Three root ideas, each an interface, each with a handful of implementations:

            Collection                          Map (separate branch!)
           ╱     │     ╲                             │
        List    Set    Queue/Deque              HashMap
         │       │        │                     LinkedHashMap
   ArrayList  HashSet  ArrayDeque               TreeMap
   LinkedList TreeSet  PriorityQueue
              LinkedHashSet

List — ordered sequence, duplicates allowed, indexed access. “The items in a cart.”
Set — no duplicates, membership is the point. “The user IDs we’ve already processed.”
Map — key → value lookup. Not technically a Collection, but the framework’s beating heart. “Order ID to Order.”
Queue/Deque — elements enter and leave in a discipline (FIFO, LIFO, priority). “Jobs waiting to run.”

The interfaces matter more than the classes, because idiomatic Java declares the interface and instantiates the implementation — the program-to-an-interface habit:

List<String> names = new ArrayList<>();     // can swap implementation later
Map<String, Order> orders = new HashMap<>();

The <> is generics — compile-time element typing, so names.add(42) won’t compile and names.get(0) needs no cast. Generics get their own deep dive; for now, always parameterize.

List: ArrayList and When LinkedList Actually Loses

List<String> cities = new ArrayList<>();
cities.add("Delhi");
cities.add("Mumbai");
cities.add(1, "Pune");          // insert at index — shifts the rest
cities.get(0);                   // "Delhi", O(1)
cities.remove("Mumbai");         // first occurrence, by equals()
cities.contains("Pune");         // true — but O(n), scans the list

ArrayList is a resizable array: instant indexed access, appends that are O(1) amortized (it grows by ~1.5× when full), inserts/removes in the middle that are O(n) because elements shift.

Then there’s LinkedList, the subject of a thousand interview questions and one important practical truth: in modern Java, you essentially never want it. Yes, its middle insertion is O(1) — once you’re standing there — but getting there is an O(n) pointer walk, and its per-node allocations and scattered memory wreck CPU cache behavior. Benchmarks routinely show ArrayList winning even at LinkedList’s “own game” for realistic sizes. Know the theory for interviews; reach for ArrayList in code. (Need efficient adds/removes at both ends? That’s ArrayDeque, below.)

Operation	ArrayList	LinkedList
`get(i)`	O(1)	O(n)
add at end	O(1)*	O(1)
add/remove middle	O(n)	O(n) find + O(1) splice
memory	compact	~3× overhead

One trap worth flagging early: removing from a list while iterating it with for-each throws ConcurrentModificationException. Use list.removeIf(x -> x.isExpired()) — cleaner anyway — or an explicit Iterator with it.remove().

Set: Uniqueness, Three Flavors

Set<String> seen = new HashSet<>();
seen.add("u42");
seen.add("u42");                 // returns false, set unchanged
seen.contains("u42");            // true — O(1), and THIS is why sets exist

The one-line performance argument for sets: list.contains(x) scans every element; set.contains(x) hashes straight to the answer. Deduplicating or membership-testing against a list inside a loop is the classic accidental O(n²); switching the lookup side to a HashSet is often a thousand-fold speedup in real code.

The three implementations differ only in ordering:

HashSet — no order guarantees at all (and the order can even change as the set grows). Fastest. Default choice.
LinkedHashSet — remembers insertion order. Use when output order should match input order (“dedupe but keep first occurrence”).
TreeSet — keeps elements sorted, O(log n) operations, and unlocks range queries: scores.headSet(50), scores.first(), scores.ceiling(42). Requires elements to be Comparable (or a supplied Comparator).

Elements must implement equals/hashCode correctly — a set is only as trustworthy as its elements’ identity, which is exactly why records make great set members. And never mutate an object after putting it in a HashSet in a way that changes its hash — it becomes unfindable, still-present ghost data.

Map: The Workhorse

Map<String, Integer> stock = new HashMap<>();
stock.put("laptop", 12);
stock.put("laptop", 9);              // same key → overwrites, maps have unique keys
stock.get("mouse");                  // null — missing key does NOT throw
stock.getOrDefault("mouse", 0);      // 0 — say what missing means

Same ordering trio as sets: HashMap (none, fastest), LinkedHashMap (insertion order — also the raw material for LRU caches via removeEldestEntry), TreeMap (sorted keys, range queries like firstEntry, subMap).

The modern methods deserve special mention because they replace endemic boilerplate. The “group into lists” dance:

// old ritual
Map<String, List<Order>> byCity = new HashMap<>();
for (Order o : orders) {
    if (!byCity.containsKey(o.city())) byCity.put(o.city(), new ArrayList<>());
    byCity.get(o.city()).add(o);
}

// modern
for (Order o : orders) {
    byCity.computeIfAbsent(o.city(), k -> new ArrayList<>()).add(o);
}

And counting:

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

computeIfAbsent, merge, putIfAbsent, getOrDefault — learn these four and most of your map code shrinks by half. Iteration goes over entrySet() (never iterate keySet() then get each key — double lookup):

for (Map.Entry<String, Integer> e : stock.entrySet()) {
    System.out.println(e.getKey() + " → " + e.getValue());
}

How HashMap pulls off O(1) — buckets, hashing, collisions, resizing — is important enough for interviews and tuning that it gets its own guide: HashMap Internals.

Queue and Deque: Order of Processing

ArrayDeque is the answer to three questions at once:

Deque<Task> queue = new ArrayDeque<>();
queue.addLast(t1);  queue.pollFirst();   // FIFO queue
queue.push(t1);     queue.pop();         // LIFO stack — use this, NOT java.util.Stack

(java.util.Stack is a legacy class — synchronized, extends Vector, and its inheritance mistake lets you insert into the middle of a “stack.” Every modern source says the same thing: ArrayDeque for stacks.)

PriorityQueue releases elements smallest-first (by natural order or comparator) regardless of insertion order — the tool for “always process the most urgent/cheapest/earliest next”:

Queue<Job> jobs = new PriorityQueue<>(Comparator.comparing(Job::deadline));
jobs.offer(lateJob); jobs.offer(urgentJob);
jobs.poll();                             // urgentJob — earliest deadline wins

Note it’s not fully sorted internally (it’s a binary heap); only the head is guaranteed minimal.

Immutable Collections and Utility Methods

Java 9’s factory methods create compact, truly unmodifiable collections:

List<String> colors = List.of("red", "green", "blue");
Set<Integer> primes = Set.of(2, 3, 5, 7);
Map<String, Integer> ranks = Map.of("gold", 1, "silver", 2);

colors.add("pink");     // UnsupportedOperationException at runtime

Use them for constants, fixed configuration, test data, and defensive snapshots (List.copyOf(internal) — the pattern from the encapsulation guide). Two cautions: they reject null elements entirely, and the exception arrives at mutation time, not compile time — the type system can’t distinguish mutable from immutable lists.

Also in the toolbox: Collections.sort(list) / list.sort(cmp), Collections.reverse, Collections.shuffle, Collections.unmodifiableList (a read-only view — changes to the underlying list still show through, unlike copyOf).

The Selection Flowchart

Need key → value lookup?  ──────────────▶ Map
    └─ sorted keys / range queries? ─▶ TreeMap
    └─ insertion order matters?     ─▶ LinkedHashMap
    └─ otherwise                    ─▶ HashMap

Duplicates meaningless, membership is the question? ─▶ Set
    └─ sorted / range queries? ─▶ TreeSet
    └─ preserve input order?   ─▶ LinkedHashSet
    └─ otherwise               ─▶ HashSet

Processing discipline (FIFO/LIFO/priority)? ─▶ Deque / PriorityQueue

Otherwise: an ordered bunch of things ─▶ ArrayList

Plus the performance cheat sheet worth actually memorizing:

	get by index	contains	add	remove middle
ArrayList	O(1)	O(n)	O(1)*	O(n)
HashSet	—	O(1)	O(1)	O(1)
TreeSet	—	O(log n)	O(log n)	O(log n)
HashMap	O(1) by key	O(1) by key	O(1)	O(1)
ArrayDeque	—	O(n)	O(1) both ends	—

If you notice contains on an ArrayList inside a loop during code review, you’ve just found the most common collections performance bug in existence.

One Realistic Exercise

Requirements: process a stream of page-view events (userId, page); report (a) unique visitor count, (b) views per page sorted by page name, (c) the last 10 events for a debug panel.

Set<String> visitors = new HashSet<>();                 // (a) uniqueness
Map<String, Integer> viewsPerPage = new TreeMap<>();    // (b) sorted keys for free
Deque<Event> recent = new ArrayDeque<>(10);             // (c) bounded recency

void handle(Event e) {
    visitors.add(e.userId());
    viewsPerPage.merge(e.page(), 1, Integer::sum);
    if (recent.size() == 10) recent.pollFirst();
    recent.addLast(e);
}

Three requirements, three structures, each chosen by asking what question the data must answer — uniqueness, sorted aggregation, bounded order. That’s the whole skill. Notice what we didn’t do: put everything in an ArrayList and answer questions by scanning, which is how collections code goes wrong by default.

Five Collection Mistakes That Survive Code Review

These pass tests and reviews, then cost someone an afternoon later:

1. Exposing internal collections. return this.items; hands callers a live remote control for your object’s state. Return List.copyOf(items) — the encapsulation guide covers why this one line prevents a whole bug family.

2. Assuming HashMap iteration order. It works in the demo, holds for months, then a resize or JDK upgrade reorders everything and a downstream consumer that silently depended on order breaks. If order is part of the contract, encode it in the type: LinkedHashMap or TreeMap.

3. Arrays.asList surprises. It returns a fixed-size list backed by the array — add throws, and writes punch through to the original array. For a real mutable list: new ArrayList<>(Arrays.asList(...)); for an immutable one: List.of(...).

4. Using Set or Map with elements that mutate. Covered in depth in the HashMap internals guide — a hash-relevant field changing after insertion makes the entry unfindable. The prevention is structural: keys and set elements should be immutable types.

5. Choosing the structure after writing the code. The ArrayList-of-everything program grows indexOf calls, nested scans, and manual dedup — each an O(n) patch over a modeling mistake. The five minutes spent asking “what questions must this data answer?” before typing is the highest-ROI design act in day-to-day Java.

Frequently Asked Questions

When should I use arrays instead of ArrayList? Rarely, in application code: fixed-size numeric work (primitives avoid boxing overhead), interop with APIs that demand them, or performance-critical inner loops. Everywhere else, ArrayList’s flexibility wins. Note that arrays and collections have different toolkits (Arrays.sort vs list.sort) and awkward conversions, so pick one world per feature and stay in it.

Why doesn’t Map extend Collection? A map is structurally a different thing — pairs, not elements. The bridge methods are keySet(), values(), and entrySet(), which give you Collection views of a map’s contents; those views are live, so removing from keySet() removes from the map.

Is Vector/Hashtable ever the right choice? No — they’re 1990s classes kept for compatibility, synchronized on every call (slow) without providing the compound-operation atomicity concurrent code actually needs. Single-threaded: ArrayList/HashMap. Multi-threaded: ConcurrentHashMap, CopyOnWriteArrayList, or explicit synchronization — see the concurrency guide.

How do I sort a Map by values? You don’t — no map implementation orders by value. You stream the entrySet, sort by value, and collect into a LinkedHashMap to freeze the order; the exact recipe is in the streams guide.

What size should I pass to new ArrayList<>(n)? The expected element count, when you know it — it pre-allocates the backing array and skips the intermediate growth copies. Unlike HashMap’s load-factor arithmetic, no adjustment needed: 10,000 expected elements → new ArrayList<>(10_000). When you don’t know, the default is fine; growth is amortized O(1) and rarely worth worrying about below hot paths.

Are there immutable views that update with the source? Yes — Collections.unmodifiableList(inner) wraps without copying: readers can’t mutate through the view, but changes to inner remain visible. That’s occasionally exactly right (a live read-only window) and occasionally a bug (you wanted a snapshot — use List.copyOf). Know which one you’re handing out.

Next: inside the machine — HashMap Internals, where buckets, hash spreading, treeification, and load factors explain how O(1) is actually achieved (and when it isn’t).