Collections & Lists

The Collections framework, ArrayList vs LinkedList, Iterator, removeIf, immutable lists and queues.

Arrays have a fixed size. Real programs need collections that grow and shrink: a shopping cart, a to-do list, search results. The Collections framework (java.util) provides ready-made, well-tested data structures. This lesson gives an overview of the framework and then focuses on the one you will use most: List.

The Collections framework at a glance#

Output

Iterable
└── Collection
    ├── List          ordered, allows duplicates, index-based   → ArrayList, LinkedList
    ├── Set           no duplicates                             → HashSet, LinkedHashSet, TreeSet
    └── Queue         processing order (FIFO, priority)         → ArrayDeque, PriorityQueue, LinkedList
        └── Deque     double-ended queue                        → ArrayDeque, LinkedList

Map (separate hierarchy) key → value                            → HashMap, LinkedHashMap, TreeMap

Interfaces (List, Set, Map) define behaviour.
Implementations (ArrayList, HashSet...) choose a data structure with different performance trade-offs.
Utility classes: Collections and Arrays hold static helpers (sort, shuffle, unmodifiable views...).

Program to the interface: List<String> names = new ArrayList<>();

`ArrayList` basics#

ListBasics.java

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

public class ListBasics {
    public static void main(String[] args) {
        List<String> tasks = new ArrayList<>();
        tasks.add("Write code");            // append
        tasks.add("Test code");
        tasks.add(0, "Plan");               // insert at index 0
        tasks.add("Test code");             // duplicates are allowed

        System.out.println(tasks);
        System.out.println(tasks.size());
        System.out.println(tasks.get(1));            // by index
        System.out.println(tasks.contains("Plan"));
        System.out.println(tasks.indexOf("Test code") + " " + tasks.lastIndexOf("Test code"));

        tasks.set(1, "Write clean code");   // replace
        tasks.remove("Test code");          // removes the FIRST match
        tasks.remove(0);                    // removes by index
        System.out.println(tasks);

        System.out.println(tasks.isEmpty());
        tasks.clear();
        System.out.println(tasks.isEmpty());
    }
}

Output

[Plan, Write code, Test code, Test code]
4
Write code
true
2 3
[Write clean code, Test code]
false
true

A List keeps elements in insertion order, allows duplicates, and gives index access from 0 to size() - 1. get with a bad index throws IndexOutOfBoundsException.

Looping over a list#

Looping.java

import java.util.List;

public class Looping {
    public static void main(String[] args) {
        List<String> langs = List.of("Java", "Kotlin", "Scala");

        for (String l : langs) System.out.print(l + " ");       // for-each
        System.out.println();

        for (int i = 0; i < langs.size(); i++) {                // with index
            System.out.print(i + ":" + langs.get(i) + " ");
        }
        System.out.println();

        langs.forEach(l -> System.out.print(l.length() + " "));  // lambda (Java 8+)
        System.out.println();
    }
}

Output

Java Kotlin Scala
0:Java 1:Kotlin 2:Scala
4 6 5

`Iterator`: the engine behind for-each#

Every collection provides an Iterator, an object that walks through elements one by one with hasNext() and next(). The for-each loop is just syntax that uses one. You need the iterator explicitly when removing during iteration:

Removing.java

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;

public class Removing {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));

        try {
            for (Integer n : nums) {
                if (n % 2 == 0) nums.remove(n);    // modifying behind the iterator's back
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("ConcurrentModificationException!");
        }

        nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
        Iterator<Integer> it = nums.iterator();
        while (it.hasNext()) {
            int n = it.next();
            if (n % 2 == 0) it.remove();           // safe removal
        }
        System.out.println(nums);

        List<String> words = new ArrayList<>(List.of("a", "", "b", " ", "c"));
        words.removeIf(String::isBlank);           // modern one-liner (Java 8+)
        System.out.println(words);
    }
}

Output

ConcurrentModificationException!
[1, 3, 5]
[a, b, c]

Collections' iterators are fail-fast: they detect structural changes made outside the iterator and throw ConcurrentModificationException rather than misbehave. Prefer removeIf in modern code.

ListIterator goes further: it can move backwards (hasPrevious, previous) and replace (set) or insert (add) elements while iterating.

Sorting and other utilities#

Sorting.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Sorting {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Mira", "al", "Zed", "bob"));

        Collections.sort(names);                               // natural order (uppercase first)
        System.out.println(names);

        names.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println(names);

        names.sort(Comparator.comparing(String::length).reversed());
        System.out.println(names);

        List<Integer> nums = new ArrayList<>(List.of(5, 3, 9, 1));
        System.out.println(Collections.max(nums) + " " + Collections.min(nums));
        Collections.reverse(nums);
        System.out.println(nums);
        Collections.swap(nums, 0, 3);
        System.out.println(nums);
        System.out.println(Collections.frequency(List.of(1, 2, 1, 1), 1));
    }
}

Output

[Mira, Zed, al, bob]
[al, bob, Mira, Zed]
[Mira, bob, Zed, al]
9 1
[1, 9, 3, 5]
[5, 9, 3, 1]
3

Sorting is stable: equal elements (like bob and Zed, both length 3) keep their relative order. Comparators get their own lesson soon.

Java 21: sequenced collections#

Java 21 added the SequencedCollection interface, giving lists (and other ordered collections) uniform first/last methods:

Sequenced.java

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

public class Sequenced {
    public static void main(String[] args) {
        List<String> queue = new ArrayList<>(List.of("b", "c"));
        queue.addFirst("a");
        queue.addLast("d");
        System.out.println(queue.getFirst() + " " + queue.getLast());
        System.out.println(queue.reversed());      // a reversed VIEW
        queue.removeFirst();
        System.out.println(queue);
    }
}

Output

a d
[d, c, b, a]
[b, c, d]

No more list.get(list.size() - 1).

Immutable lists#

Immutable.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Immutable {
    public static void main(String[] args) {
        List<String> fixed = List.of("red", "green");          // unmodifiable, no nulls allowed
        try {
            fixed.add("blue");
        } catch (UnsupportedOperationException e) {
            System.out.println("List.of is unmodifiable");
        }

        List<String> mutable = new ArrayList<>(fixed);         // mutable copy
        mutable.add("blue");
        System.out.println(mutable);

        List<String> snapshot = List.copyOf(mutable);          // unmodifiable copy
        List<String> view = Collections.unmodifiableList(mutable);  // read-only VIEW
        mutable.add("pink");
        System.out.println(snapshot.size() + " " + view.size());

        List<String> fromArray = Arrays.asList("x", "y");      // fixed-size, backed by the array
        fromArray.set(0, "z");                                 // allowed
        System.out.println(fromArray);
    }
}

Output

List.of is unmodifiable
[red, green, blue]
3 4
[z, y]

Creation	Add/remove	Set	Nulls
`new ArrayList<>()`	✅	✅	✅
`List.of(...)`, `List.copyOf(...)`	❌	❌	❌
`Arrays.asList(...)`	❌ (fixed size)	✅	✅
`Collections.unmodifiableList(x)`	❌, but reflects changes to `x`	❌	✅

Returning unmodifiable lists from your methods prevents callers from corrupting your object's state.

`ArrayList` vs `LinkedList`#

ArrayList stores elements in a resizable array. When full, it allocates a bigger one (about 1.5×) and copies.
LinkedList stores a chain of nodes, each pointing to the next and previous node.

Operation	`ArrayList`	`LinkedList`
`get(i)` / `set(i)`	O(1)	O(n)
add/remove at the end	O(1) amortised	O(1)
add/remove at the front	O(n) (shifts everything)	O(1)
add/remove in the middle	O(n)	O(n) to find the spot, O(1) to link
memory per element	small	large (node objects + two pointers)
CPU cache friendliness	excellent	poor

In practice, use ArrayList by default. Its contiguous memory makes it faster than LinkedList for almost everything, even many middle insertions. If you need fast operations at both ends, use ArrayDeque, not LinkedList.

Tip: if you know roughly how many elements you will add, new ArrayList<>(10_000) avoids repeated resizing.

Queues and deques#

A Queue hands elements out in a processing order; a Deque ("deck") works at both ends, so it can be a queue or a stack:

Queues.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Queue;

public class Queues {
    public static void main(String[] args) {
        Queue<String> line = new ArrayDeque<>();        // FIFO: first in, first out
        line.offer("Asha");
        line.offer("Ben");
        line.offer("Chen");
        System.out.println(line.peek() + " is first");
        System.out.println(line.poll() + " served; left: " + line);

        Deque<String> stack = new ArrayDeque<>();       // LIFO: last in, first out
        stack.push("page1");
        stack.push("page2");
        stack.push("page3");
        System.out.println("Back to " + stack.pop() + ", now on " + stack.peek());

        Queue<Integer> tasks = new PriorityQueue<>();    // smallest first
        tasks.offer(5);
        tasks.offer(1);
        tasks.offer(3);
        StringBuilder order = new StringBuilder();
        while (!tasks.isEmpty()) order.append(tasks.poll()).append(' ');
        System.out.println(order.toString().strip());
    }
}

Output

Asha is first
Asha served; left: [Ben, Chen]
Back to page3, now on page2
1 3 5

offer/poll/peek return false/null on failure; add/remove/element throw exceptions instead.
Use ArrayDeque for stacks (instead of the legacy Stack class) and FIFO queues.
PriorityQueue always gives the smallest element first (or by a Comparator you supply). It is great for schedulers and algorithms like Dijkstra's.

Big-O in one minute#

Big-O describes how the cost of an operation grows with the number of elements n:

O(1) constant: the same speed for 10 or 10 million elements.
O(log n): grows very slowly (tree lookups, binary search).
O(n) linear: twice the elements, twice the time (scanning a list with contains).

Calling list.contains(x) inside a loop over another list is O(n²) and becomes slow with large data. A HashSet (next lesson) makes contains O(1).

Common mistakes#

Removing elements inside a for-each loop.
Confusing remove(int index) with remove(Object o) on a List<Integer>.
Modifying a List.of or Arrays.asList list.
Choosing LinkedList "because inserts are fast". Measure first; ArrayList usually wins.
Using list.contains for frequent lookups on large data. Use a Set.

What's next#

Lists allow duplicates and are slow to search. Next, sets guarantee uniqueness and offer lightning-fast membership checks.

The Collections framework at a glance#

ArrayList basics#

Looping over a list#

Iterator: the engine behind for-each#

Sorting and other utilities#

Java 21: sequenced collections#

Immutable lists#

ArrayList vs LinkedList#

Queues and deques#

Big-O in one minute#

Common mistakes#

What's next#

Quick quiz

`ArrayList` basics#

`Iterator`: the engine behind for-each#

`ArrayList` vs `LinkedList`#