Lists and Sets

Arrays are fast and simple and have one big limitation: their size is fixed when you create them. Real programs deal with groups of things whose size changes: the orders in a basket, the unique email addresses on a mailing list, the interview rounds scheduled so far. You need containers that grow, shrink, search and reject duplicates.

Java's standard library gives you a family of these, called the Java Collections Framework. This article covers its two most common members: lists (ordered, duplicates allowed) and sets (no duplicates). The next two articles cover maps and queues, and then generics, which is what the angle brackets mean.

• How the framework is organised, and why you declare variables by interface.
• How ArrayList and LinkedList work, and how to choose.
• What makes a set unique, and how its three main implementations differ.
• How to iterate and remove safely.
• The differences between immutable lists, fixed-size lists and read-only views.
• The new methods for ordered collections in Java 21.

The framework is built from interfaces (what a collection can do) and implementations (how it does it).

Iterable  `-- Collection        |-- List     (ordered, indexed, duplicates allowed)   ArrayList, LinkedList        |-- Set      (no duplicates)                           HashSet, LinkedHashSet, TreeSet        `-- Queue    (ordered for processing)                  ArrayDeque, PriorityQueue, LinkedListMap (separate: key to value)                                   HashMap, LinkedHashMap, TreeMap

A Map is not a Collection, because it stores pairs. Article 12 covers it.

The most important habit is to declare variables with the interface type and choose the implementation only where you create the object:

List<String> names = new ArrayList<>();      // good: the rest of the code only knows ListArrayList<String> tied = new ArrayList<>();   // avoid: needlessly tied to one implementation

This is the polymorphism from article 6 paying off: if you later find that a different list suits you better, one line changes. The <String> is a type parameter, saying "a list of strings", and it lets the compiler stop you from adding a number to it. Article 14 explains how that works.

A List keeps elements in the order you put them in, lets you reach any element by index (starting at 0), and allows duplicates. The two classic implementations are built very differently.

ArrayList stores its elements in a plain array internally, and replaces it with a bigger array when it fills up. Oracle's documentation says size, isEmpty, get and set run in constant time, and add runs in amortised constant time (growing the array occasionally is paid for by the many cheap adds), while most other operations are linear.

LinkedList is a doubly linked list: each element is wrapped in a node that points to the previous and next nodes. Its documentation notes that operations indexing into the list traverse from the beginning or the end, whichever is closer, so get(i) has to walk the chain.

The honest guidance: use ArrayList unless you have a measured reason not to. Beginners are often taught that LinkedList is "faster for insertion", but that is only true when you already hold the position (for example with an iterator), and in practice array-based storage is usually faster even for many insert-and-remove patterns, because arrays are laid out contiguously in memory and walking linked nodes is slow. If you need to add and remove at both ends, ArrayDeque (article 13) is normally a better choice than LinkedList. You still need to know both for interviews, and to understand the trade-offs they illustrate.

// File: Main.javaimport java.util.ArrayList;import java.util.Collections;import java.util.List;public class Main {    public static void main(String[] args) {        List<String> languages = new ArrayList<>();        languages.add("Java");        languages.add("Python");        languages.add("Go");        languages.add(1, "Kotlin");               // insert at index 1        languages.set(0, "Java 21");              // replace        System.out.println(languages + " size=" + languages.size());        System.out.println(languages.get(2) + " " + languages.indexOf("Go") + " " + languages.contains("Rust"));        languages.remove("Python");               // remove by value        languages.remove(0);                      // remove by index        System.out.println(languages);        List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 40));        numbers.remove(1);                        // index 1: removes the value 20        numbers.remove(Integer.valueOf(40));      // the object 40        System.out.println(numbers);        List<Integer> scores = new ArrayList<>(List.of(5, 3, 9, 1));        Collections.sort(scores);        System.out.println(scores + " max=" + Collections.max(scores));        scores.sort(Collections.reverseOrder());        System.out.println(scores);        List<Integer> view = scores.subList(1, 3);   // a view of part of the list        view.set(0, 99);        System.out.println(scores);    }}

[Java 21, Kotlin, Python, Go] size=4Python 3 false[Kotlin, Go][10, 30][1, 3, 5, 9] max=9[9, 5, 3, 1][9, 99, 3, 1]

Two things to take from this program. First, the trap with List<Integer>: numbers.remove(1) removes the element at index 1, while numbers.remove(Integer.valueOf(40)) removes the object 40. With a list of integers, the two overloads look similar and mean different things. Second, subList returns a view, not a copy: changing the view changed the original list (the 9 became 99). Views are cheap and convenient, and a classic source of surprise.

You cannot change a list's structure (add or remove) while iterating over it with a for-each loop. Java's iterators are fail-fast: the documentation says that if the list is structurally modified after the iterator is created, other than through the iterator's own methods, the iterator throws ConcurrentModificationException. This is a bug detector, not a feature to rely on.

// File: Main.javaimport java.util.ArrayList;import java.util.Iterator;import java.util.List;public class Main {    public static void main(String[] args) {        List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));        try {            for (Integer n : numbers) {                if (n % 2 == 0) {                    numbers.remove(n);               // modifies during iteration                }            }        } catch (java.util.ConcurrentModificationException e) {            System.out.println("ConcurrentModificationException caught");        }        List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));        a.removeIf(n -> n % 2 == 0);                 // best: declarative        System.out.println(a);        List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));        Iterator<Integer> it = b.iterator();        while (it.hasNext()) {            if (it.next() % 2 == 0) {                it.remove();                         // the iterator's own remove is allowed            }        }        System.out.println(b);    }}

ConcurrentModificationException caught[1, 3, 5][1, 3, 5]

There are three safe approaches: removeIf with a condition (the simplest, using a lambda that article 15 explains), the iterator's own remove, or building a new list of the items to keep. (Removing in a for-each does not always throw, which is worse: whether it does depends on where in the list you are, so a test might pass by luck.)

These three look similar and behave differently, and are a frequent source of bugs and interview questions.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main {    static void tryAdd(String label, List<String> list) {        try {            list.add("new");            System.out.println(label + ": add worked");        } catch (UnsupportedOperationException e) {            System.out.println(label + ": add not supported");        }    }    public static void main(String[] args) {        List<String> source = new ArrayList<>(List.of("a", "b"));        List<String> immutable = List.of("a", "b");                    // truly unmodifiable        List<String> copy = List.copyOf(source);                       // unmodifiable snapshot        List<String> fixedSize = Arrays.asList("a", "b");              // fixed size, writes through        List<String> readOnlyView = Collections.unmodifiableList(source);  // read-only view        tryAdd("List.of", immutable);        tryAdd("List.copyOf", copy);        tryAdd("Arrays.asList", fixedSize);        tryAdd("unmodifiableList", readOnlyView);        fixedSize.set(0, "changed");                                   // allowed        source.add("c");                                               // the original changes        System.out.println(fixedSize + " " + copy + " " + readOnlyView);        try {            List.of("a", null);        } catch (NullPointerException e) {            System.out.println("List.of rejects null");        }    }}

List.of: add not supportedList.copyOf: add not supportedArrays.asList: add not supportedunmodifiableList: add not supported[changed, b] [a, b] [a, b, c]List.of rejects null

List.of and List.copyOf (Java 9 and 10) are what you want for a truly immutable list: the documentation lists them as unmodifiable, disallowing null, and with elements staying in the order given. Remember that "unmodifiable" is about the list, not its contents. If the elements are mutable objects, they can still change. Arrays.asList is the older style that you will see everywhere in code written before Java 9. It is fine for a fixed-size view of an array, and it is not the same as an immutable list. For returning a list from a method without exposing your internal one, use List.copyOf (a snapshot) or Collections.unmodifiableList (a live read-only view), and decide which you mean.

A Set is a collection that contains no duplicate elements. "Duplicate" is decided by the element class's equals (and hashCode) for the hash-based sets, so article 7 matters directly here. The three main implementations differ in how they order their elements.

// File: Main.javaimport java.util.HashSet;import java.util.LinkedHashSet;import java.util.Set;import java.util.TreeSet;public class Main {    public static void main(String[] args) {        String[] input = {"delta", "alpha", "charlie", "alpha", "bravo", "delta"};        Set<String> hash = new HashSet<>();        Set<String> linked = new LinkedHashSet<>();        Set<String> sorted = new TreeSet<>();        for (String s : input) {            System.out.print(hash.add(s) + " ");    // add returns false for a duplicate            linked.add(s);            sorted.add(s);        }        System.out.println();        System.out.println("hash size: " + hash.size() + ", contains bravo: " + hash.contains("bravo"));        System.out.println("insertion order: " + linked);        System.out.println("sorted order:    " + sorted);        Set<Integer> a = new TreeSet<>(Set.of(1, 2, 3, 4));        Set<Integer> b = new TreeSet<>(Set.of(3, 4, 5));        Set<Integer> union = new TreeSet<>(a);        union.addAll(b);        Set<Integer> intersection = new TreeSet<>(a);        intersection.retainAll(b);        Set<Integer> difference = new TreeSet<>(a);        difference.removeAll(b);        System.out.println(union + " " + intersection + " " + difference);    }}

true true true false true falsehash size: 4, contains bravo: trueinsertion order: [delta, alpha, charlie, bravo]sorted order:    [alpha, bravo, charlie, delta][1, 2, 3, 4, 5] [3, 4] [1, 2]

add returns a boolean: true if the element was new, false if it was already present. That return value is a handy way to detect duplicates. I printed the HashSet's size and a lookup but not its contents on purpose: do not rely on the iteration order of a HashSet. It is unspecified, can look sorted by accident for small inputs, and can change between runs or Java versions. If you need order, choose a set that defines one. The bottom line shows the standard set operations: addAll for union, retainAll for intersection, removeAll for difference. A HashSet is internally built on a hash map (article 12), which is why it needs a correct hashCode.

A very common use of a HashSet is removing duplicates or fast membership checks: new HashSet<>(list) removes duplicates, and set.contains(x) is much faster than list.contains(x) for large collections, because the list has to scan.

Before Java 21, getting the first or last element of a collection was different for every type: list.get(0) and list.get(list.size() - 1) for a list, first() and last() for a SortedSet, nothing at all for a LinkedHashSet. JEP 431 (final in Java 21) added the SequencedCollection interfaces, giving every collection with a defined encounter order the same methods: getFirst(), getLast(), addFirst, addLast, removeFirst, removeLast and reversed().

// File: Main.javaimport java.util.ArrayList;import java.util.LinkedHashSet;import java.util.List;import java.util.SequencedSet;public class Main {    public static void main(String[] args) {        List<String> stages = new ArrayList<>(List.of("applied", "screening", "interview"));        System.out.println(stages.getFirst() + " " + stages.getLast());        System.out.println(stages.reversed());        SequencedSet<String> tags = new LinkedHashSet<>(List.of("java", "spring", "sql"));        System.out.println(tags.reversed() + " first=" + tags.getFirst());    }}

applied interview[interview, screening, applied][sql, spring, java] first=java

On older Java you would write stages.get(stages.size() - 1) and risk an off-by-one error. getFirst and getLast on an empty list throw NoSuchElementException. They need Java 21, which is this course's baseline, so you can use them freely here but not on Java 17.

• Modifying a list while looping over it with for-each.
• Confusing remove(int index) and remove(Object) on a List<Integer>.
• Using LinkedList for random access because it was described as "good for insertion".
• Assuming Arrays.asList returns an immutable list.
• Returning your internal list from a getter, letting callers change it.
• Relying on HashSet order.
• Putting objects with a missing or broken hashCode into a HashSet.
• Using list.contains in a loop on big lists where a set would do (accidental quadratic work).
• Mutating an element that sits in a set in a way that changes its hashCode.

list.removeIf(String::isBlank);

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

• Next: Maps and How HashMap Works explains key-value collections and the hashing machinery that HashSet is built on.
• For sorting and queues: Ordering, Queues and Choosing a Collection.
• For what the angle brackets mean: Generics: Type Safety, Wildcards and Erasure.