Collections Framework Part 1: List and Set

Executive Summary

The Collections Framework separates contracts (List, Set, Queue, Map) from implementations, so code depends on behavior while you swap the engine. Use List when order and index access matter and duplicates are legal: ArrayList is the default choice, because its array-backed random access and compact memory beat LinkedList in nearly every real workload. Use Set when uniqueness matters or membership tests run often: HashSet for speed without order, LinkedHashSet for stable insertion order, TreeSet for sorted iteration at O(log n) cost. Never mutate a collection while iterating it with for-each; use removeIf, which Part 3’s lambdas article explains fully. Prefer List.of and Set.of for fixed immutable collections. The next article adds Map and Queue; the one after prices all of them against each other.

The Collections Framework at a Glance

The framework’s one architectural idea is worth naming before any syntax: the interfaces are the contracts. In contrast, the classes are the engines. Your method signatures speak List and Set; your constructors choose ArrayList or HashSet. Consequently, swapping an implementation is a one-line change. Also, the performance tables in this article are the menu you order from. If you want the quick beginner tour of List, Set, and Map first, the Java Mini Series post on collections covers ArrayList and HashMap in one sitting.

  Collection (interface)
     |
     +-- List: ordered, indexed, duplicates allowed
     |     +-- ArrayList       array-backed, fast random access
     |     +-- LinkedList      doubly-linked, rarely the right choice
     |
     +-- Set: unique elements, at most one null
     |     +-- HashSet         hash table, no iteration order
     |     +-- LinkedHashSet   hash table, insertion order preserved
     |     +-- TreeSet         red-black tree, sorted iteration
     |
     +-- Queue: FIFO and beyond (next article)
           +-- ArrayDeque ...

  Map: unique keys to values, its own tree (next article)
        +-- HashMap, TreeMap, LinkedHashMap ...

Every interface guarantees behavior; every implementation prices it:

Interface	Guarantees	Duplicates	Default implementation
List	Order, index access	Allowed	ArrayList
Set	Uniqueness	Refused (add returns false)	HashSet
Queue	Processing order	Allowed	ArrayDeque (next article)
Map	Key to value, unique keys	Keys unique, values free	HashMap (next article)

List in Java: Ordered, Indexed, Duplicates Allowed

A List is what an array wanted to be when it grew up: ordered, index-accessible, and resizable at runtime. The List interface defines the contract. ArrayList implements it with a backing array that grows by amortized doubling, exactly the mechanism you hand-rolled in Part 1 when you resized arrays with Arrays.copyOf.

import java.util.ArrayList;
import java.util.List;

List<String> names = new ArrayList<>();   // declare List, construct ArrayList
names.add("Ada");                          // [Ada]
names.add("Linus");                        // [Ada, Linus]
names.add("Ada");                          // [Ada, Linus, Ada]: duplicates fine

names.set(0, "Grace");                     // replace by index: [Grace, Linus, Ada]
System.out.println(names.get(1));         // Linus: O(1) random access
System.out.println(names.indexOf("Ada")); // 2: first occurrence, or -1
System.out.println(names.size());         // 3

for (String name : names) {               // iteration in list order
    System.out.println("hello, " + name);
}

List<String> fixed = List.of("a", "b");   // immutable: add throws

Three habits follow from that block. Declare with the interface type (List, not ArrayList) so implementations stay swappable. Read with get when you need the index, and iterate otherwise. And know that List.of produces an immutable list, the right default for fixed data and the wrong choice for anything that grows.

ArrayList vs LinkedList: The Verdict Table

However, LinkedList is the collection interviewers love and production almost never uses. The table explains both halves:

Operation	ArrayList	LinkedList
get(i) random access	O(1)	O(n): walk the chain
add at the end	O(1) amortized	O(1)
insert in the middle	O(n): shift elements	O(n) find plus O(1) relink
remove by index	O(n)	O(n)
Memory per element	Compact, contiguous	A node object per element
Realistic winner	Almost always	When a profiler proves it

The nuance the table hides: LinkedList’s O(1) insert only counts the relink, not the O(n) walk to find the position. Also, its per-element memory overhead plus pointer chasing usually erase the theoretical edge even then. Consequently, the professional rule is simple: use ArrayList unless a profiler shows a specific reason. Also, ArrayDeque (next article) covers the queue cases where a linked structure genuinely fits.

The Mutation Trap: Removing While Iterating

Every Java developer meets ConcurrentModificationException exactly once, usually on their first week of collections. Wrong code first:

// WRONG: structural change during for-each iteration
for (String name : names) {
    if (name.startsWith("L")) {
        names.remove(name);    // ConcurrentModificationException
    }
}

// RIGHT: one predicate-driven pass, no manual iteration
names.removeIf(name -> name.startsWith("L"));
// names is now [Grace, Ada]

The delta: for-each uses an internal iterator that expects the list to hold still. So, any structural change after iteration begins trips the check. Instead, removeIf does the scan and removal internally in one safe pass. The arrow syntax is a lambda, a taste of Part 3’s lambda article. For now, read name -> name.startsWith(“L”) as “the condition under which we keep scanning and removing”.

Set in Java: Uniqueness with Attitude

A Set refuses duplicates, and the refusal is the feature. The Set contract says add returns false instead of adding a second copy, contains answers in O(1) for hash-based sets, and equality of elements is judged by the equals and hashCode pair from the Object article.

import java.util.HashSet;
import java.util.Set;

Set<String> seen = new HashSet<>();
System.out.println(seen.add("ada"));    // true:  added
System.out.println(seen.add("ada"));    // false: refused, size still 1
System.out.println(seen.contains("ada")); // true: O(1) bucket check

Set<String> fixed = Set.of("x", "y");   // immutable, and duplicates are a
                                        // compile-time error here, not a false return

Uniqueness leans on your equals and hashCode discipline: two Money records with the same fields dedupe correctly because the pair is generated correctly. A class with identity equals never dedupes, which is why the Object article’s “override the pair together” rule is a collections rule in disguise.

HashSet vs LinkedHashSet vs TreeSet

Implementation	add / contains / remove	Iteration order	Nulls	Notes
HashSet	O(1)	Unspecified	One null allowed	The default; needs good hashCode
LinkedHashSet	O(1)	Insertion order	One null allowed	Slightly more memory
TreeSet	O(log n)	Sorted	No nulls	Needs Comparable or a Comparator

TreeSet is really the NavigableSet interface’s implementation. Also, it offers first(), last(), floor(), and ceiling() for range queries, at logarithmic cost. For enum-typed sets, none of these: EnumSet from the enums article beats them all with its bit vector.

Choosing Between List and Set: The Complete Example

One program shows every implementation earning its place. A raw list with duplicates goes through three sets, each answering a different question:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.TreeSet;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<String> raw = new ArrayList<>();
        raw.addAll(List.of("linus", "ada", "grace", "ada", "linus"));
        System.out.println("raw list:        " + raw);

        Set<String> hash = new HashSet<>(raw);
        System.out.println("HashSet:         " + hash + "  (order unspecified)");

        var stable = new LinkedHashSet<String>(raw);
        System.out.println("LinkedHashSet:   " + stable + "  (first-seen order)");

        var sorted = new TreeSet<String>(raw);
        System.out.println("TreeSet:         " + sorted + "  (sorted)");
    }
}

raw list:        [linus, ada, grace, ada, linus]
HashSet:         [ada, grace, linus]  (order unspecified)
LinkedHashSet:   [linus, ada, grace]  (first-seen order)
TreeSet:         [ada, grace, linus]  (sorted)

In short, the same input, three different sets, three different guarantees: fast and unordered, stable and first-seen, sorted. Every collection choice in the rest of this course reduces to picking the guarantee your use case actually needs.

How Real Systems Do This

Production Java leans on these two interfaces constantly, in recognizable shapes. Deduplication is the List-to-Set round trip: collect into a List, construct a HashSet from it, and continue with unique values, exactly the demo above. Membership tracking uses a HashSet as a “seen” accumulator, for example request IDs in an at-least-once processing loop, where contains is the whole point and order is irrelevant. Fixed reference data ships as List.of or Set.of, because immutable collections are safe to share across code with no defensive copies.

The intro’s 90-second endpoint deserves its anatomy, because the shape is everywhere. The code walked a List of 40,000 user IDs and called contains for every incoming request, which is O(n) per request and O(n squared) under load. However, one constructor change, List to HashSet, made contains O(1) and the endpoint dropped to 40 milliseconds. In my experience, when a collection-backed service is slow, the culprit is a contains on a List in a loop more often than any database issue.

The library practice from Part 2 already used these tools quietly: LoanService held List<Loan> and List<LibraryEvent> behind ArrayLists, and events() returned List.copyOf as an unmodifiable view. So, now you know why each line was shaped that way: the interface in the signature, the engine in the constructor, the immutable barrier at the boundary.

Decision Framework

Ask these in order, and the collection picks itself.

1. Do duplicates carry meaning (a history, a queue of actions, positional data)? List. Is uniqueness a rule of the domain? Set.
2. Do you need index access or stable positional order? List, and ArrayList.
3. Do you need sorted iteration or range queries? TreeSet, or sort a List when sorting is a one-off.
4. Must iteration order match insertion order, duplicates aside? LinkedHashSet.
5. Are membership tests frequent relative to size? Set, regardless of the duplicate question; a List contains is O(n) every time.
6. Is the data fixed at compile time? List.of or Set.of, immutable by construction.
7. Is the element type an enum? EnumSet or EnumMap, from the enums article, beats everything here.

When NOT to Use This

• Do not box primitives into collections on hot paths. List<Integer> allocates an Integer per element; int[] arrays are dramatically lighter. Also, Part 3’s streams article revisits this trade with numbers.
• Do not reach for LinkedList as the “fast insert” default. Its insert cost includes the O(n) walk, and its per-element memory usually loses to ArrayList even in insert-heavy workloads.
• Do not use collections for two-element or three-element fixed shapes. Records and small classes say what the fields mean; a List<Object> with positional conventions says nothing forever.

Common Mistakes

• Removing elements from a List during for-each iteration. ConcurrentModificationException is the kind failure; the silent variant is removing through an index loop that skips elements. Use removeIf.
• Calling contains on a List inside a loop. Each check walks the list, and the product is quadratic; a HashSet turns the loop linear.
• Storing mutable objects in a HashSet and mutating their hashCode fields afterward. The element becomes unfindable, the ghost-entry bug from the Object article.
• Expecting HashSet iteration order to be stable. It is unspecified, changes across JDK versions, and any code depending on it is a time bomb. Instead, use LinkedHashSet for stable order.
• Adding nulls and then calling TreeSet operations that must compare them: TreeSet rejects nulls entirely. So, the failure is a NullPointerException at a distance.
• Trying to modify List.of or Set.of results. They are immutable by design; UnsupportedOperationException is the reminder, and the fix is a new collection, not a mutation.

Key Takeaways

• Collections separate contract from engine: declare List and Set, construct ArrayList and HashSet, and swap implementations in one line.
• ArrayList is the default List: O(1) random access, compact memory. LinkedList needs a profiler’s permission.
• Sets refuse duplicates and answer contains in O(1): HashSet by default, LinkedHashSet for insertion order, TreeSet for sorted order and range queries.
• Set behavior depends on your equals and hashCode; records and correct pairs make uniqueness trustworthy.
• Never remove from a collection during for-each iteration; removeIf does it in one safe pass.
• List.of and Set.of give immutability for fixed data, free of defensive-copy ceremony.
• Membership tests against a List inside a loop are the classic quadratic bug; the Set swap is a one-line fix.

FAQ

What is the difference between List and Set in Java?

A List is ordered and indexed, and duplicates are allowed; a Set refuses duplicates and, with hash-based implementations, answers contains in constant time. Order with repeats, or uniqueness with fast membership: the domain decides which.

When should I use LinkedList instead of ArrayList?

Almost never. LinkedList’s O(1) insert needs the O(n) walk to the position first, and its per-element node overhead usually loses to ArrayList’s compact array. Use ArrayList by default and demand profiler evidence for anything else.

Why does HashSet need equals and hashCode?

Because it locates elements by hashCode bucket and confirms matches with equals. Equal elements must hash alike or the set stores duplicates and loses them on lookup, the exact contract from the Object article.

What is the difference between HashSet and TreeSet?

HashSet hashes: O(1) operations and unspecified iteration order. TreeSet keeps a sorted red-black tree: O(log n) operations, sorted iteration, and range methods like floor and ceiling, at the cost of requiring Comparable elements.

How do I remove elements from a List while iterating in Java?

Use removeIf with a condition; it performs the scan and removal in one internal pass. Removing directly during for-each triggers ConcurrentModificationException, and index-loop removal skips elements.

Conclusion

List and Set are the two shapes that carry most production data: order and position on one side, uniqueness and fast membership on the other. The implementations price those guarantees differently, and now you have the tables to choose with intent instead of habit.

The next article completes the framework with Map and Queue: key-to-value lookup, the workhorse of caches and indexes, and the processing orders behind schedulers and buffers.

Order with ArrayList, uniqueness with HashSet, and let the contract, not the habit, choose.

Last updated on 23 September 2026.