Lists, Deques, and Iteration

This lesson covers the list and deque implementations in java.util, how they store elements, and how iteration detects modification. After it, a reader can choose between ArrayList, LinkedList, and ArrayDeque from their memory layout and explain the exceptions they throw.

Type	Storage	Typical use
`ArrayList`	One `Object[]`, grows by about 1.5x	Default `List`
`LinkedList`	Doubly linked nodes	Rarely the right choice
`ArrayDeque`	Circular `Object[]`	Stack and FIFO queue
`List.of`	Immutable, compact classes	Constants, return values
`Arrays.asList`	Fixed-size view over an array	Wrapping an existing array

The interfaces form this hierarchy (Java 21 added the Sequenced* interfaces):

Text

Iterable
 └── Collection
      ├── SequencedCollection        (Java 21)
      │    ├── List
      │    ├── Deque  (extends Queue)
      │    └── SequencedSet ── SortedSet ── NavigableSet
      ├── Set
      └── Queue
Map ── SequencedMap (Java 21) ── SortedMap ── NavigableMap

Example 1: ArrayList growth

An ArrayList keeps its elements in an Object[] field named elementData and a size. Capacity is the array length; size is the number of elements in use. The JDK 25 source of ArrayList.grow creates a 10-slot array on the first add to a list made with new ArrayList<>(), then grows by oldCapacity >> 1 (half the old capacity) each time the array is full. The example reads the private field by reflection, which needs --add-opens java.base/java.util=ALL-UNNAMED as explained in Packages, Modules, and Reflection.

Java

import java.lang.reflect.Field;
import java.util.ArrayList;

public class Growth {
    static int capacity(ArrayList<?> list) throws Exception {
        Field f = ArrayList.class.getDeclaredField("elementData");
        f.setAccessible(true);
        return ((Object[]) f.get(list)).length;
    }

    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println("empty: capacity " + capacity(list));
        int last = -1;
        for (int i = 0; i < 100; i++) {
            list.add(i);
            int cap = capacity(list);
            if (cap != last) {
                System.out.println("size " + list.size() + " -> capacity " + cap);
                last = cap;
            }
        }
        list.trimToSize();
        System.out.println("after trimToSize: " + capacity(list));
        list.ensureCapacity(500);
        System.out.println("after ensureCapacity(500): " + capacity(list));
    }
}

Output

empty: capacity 0
size 1 -> capacity 10
size 11 -> capacity 15
size 16 -> capacity 22
size 23 -> capacity 33
size 34 -> capacity 49
size 50 -> capacity 73
size 74 -> capacity 109
after trimToSize: 100
after ensureCapacity(500): 500

The sequence 10, 15, 22, 33, 49, 73, 109 is n + n/2 each time. Each grow copies the array with Arrays.copyOf, so one add can cost O(n), but the total copy work over n adds is O(n): amortized O(1) per add. ensureCapacity grows once before a bulk insert of known size; trimToSize drops unused slots. new ArrayList<>(n) sets the initial capacity directly.

Example 2: LinkedList costs

A LinkedList stores each element in a separate node object with item, next, and prev fields. get(i) walks from the nearer end, so it is O(n). Inserting at a known node is O(1), but reaching the node is O(n) unless an iterator is already there. Each node is an extra object, and the nodes are scattered in memory, which costs cache misses (see CPU Caches and Locality).

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedCosts {
    public static void main(String[] args) {
        List<Integer> array = new ArrayList<>();
        LinkedList<Integer> linked = new LinkedList<>();
        for (int i = 0; i < 10; i++) { array.add(i); linked.add(i); }

        // Index-based loop on LinkedList: each get walks nodes.
        long steps = 0;
        for (int i = 0; i < linked.size(); i++) steps += Math.min(i, linked.size() - 1 - i) + 1;
        System.out.println("node visits for indexed loop over 10: " + steps);

        // Insert after every even element using a ListIterator: O(1) per insert.
        ListIterator<Integer> it = linked.listIterator();
        while (it.hasNext()) {
            if (it.next() % 2 == 0) it.add(-1);
        }
        System.out.println(linked);
        System.out.println("first=" + linked.getFirst() + " last=" + linked.getLast());
    }
}

Output

node visits for indexed loop over 10: 30
[0, -1, 1, 2, -1, 3, 4, -1, 5, 6, -1, 7, 8, -1, 9]
first=0 last=9

The step count models how LinkedList.node(i) walks from whichever end is closer. For n elements an indexed loop visits about n²/4 nodes. In practice ArrayList (or ArrayDeque for both ends) is faster for almost all workloads, including many middle inserts, because System.arraycopy moves contiguous memory quickly. LinkedList fits when a ListIterator stays positioned while many inserts and removes happen at that point.

Example 3: ArrayDeque as stack and queue

ArrayDeque stores elements in a circular array: head is the index of the first element, tail the index after the last, and both wrap around modulo the array length. Adding or removing at either end is O(1) and does not shift elements. It rejects null, because poll uses null to mean "empty". It replaces both Stack (synchronized, extends Vector) and LinkedList as a queue.

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeUse {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("a"); stack.push("b"); stack.push("c");     // addFirst
        System.out.println("stack pop: " + stack.pop() + stack.pop() + stack.pop());

        Deque<String> queue = new ArrayDeque<>();
        queue.offer("1"); queue.offer("2"); queue.offer("3");  // addLast
        System.out.println("queue poll: " + queue.poll() + queue.poll() + queue.poll());
        System.out.println("poll on empty: " + queue.poll());

        try {
            queue.remove();
        } catch (java.util.NoSuchElementException e) {
            System.out.println("remove on empty: NoSuchElementException");
        }
        try {
            queue.add(null);
        } catch (NullPointerException e) {
            System.out.println("null rejected");
        }

        // Balanced brackets with the deque as a stack.
        String s = "{[()()]}";
        Deque<Character> open = new ArrayDeque<>();
        boolean ok = true;
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> open.push(c);
                default -> {
                    char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
                    if (open.isEmpty() || open.pop() != expected) ok = false;
                }
            }
        }
        System.out.println(s + " balanced: " + (ok && open.isEmpty()));
    }
}

Output

stack pop: cba
queue poll: 123
poll on empty: null
remove on empty: NoSuchElementException
null rejected
{[()()]} balanced: true

Deque has two method families: offer/poll/peek return false or null on failure, and add/remove/element throw. In the JDK 25 source a default ArrayDeque starts with a 17-slot array (16 elements plus one empty slot that separates head and tail), and grows by oldCapacity + 2 while below 64 and by half above that.

Example 4: iterators and fail-fast behavior

An Iterator walks a collection with hasNext and next; the enhanced for loop compiles to one. Collections in java.util keep a counter, modCount, that every structural change (add, remove, clear) increments. The iterator records the value at creation and throws ConcurrentModificationException when it changes. This is fail-fast behavior: it detects the bug on a best-effort basis and is not a thread-safety mechanism.

Java

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

public class FailFast {
    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);     // structural change during iteration
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("ConcurrentModificationException, list now " + nums);
        }

        nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
        Iterator<Integer> it = nums.iterator();
        while (it.hasNext()) {
            if (it.next() % 2 == 0) it.remove();    // the iterator updates its expected count
        }
        System.out.println("iterator.remove: " + nums);

        List<Integer> quiet = new ArrayList<>(List.of(1, 2, 3));
        for (Integer n : quiet) {
            if (n == 2) quiet.remove(n);            // removes the second-to-last element
        }
        System.out.println("no exception, list now " + quiet);
    }
}

Output

ConcurrentModificationException, list now [1, 3, 4, 5, 6]
iterator.remove: [1, 3, 5]
no exception, list now [1, 3]

The last loop shows why fail-fast is best effort. After removing 2, size becomes 2 and the cursor is 2, so hasNext returns false and the check in next never runs. Code must not rely on the exception.

Example 5: removeIf and bulk operations

Collection.removeIf (Java 8) removes all elements matching a condition in one pass. ArrayList overrides it to mark matches first and then compact the array once, which is O(n) instead of O(n²) for repeated remove(i). The condition is passed as a lambda, n -> n % 3 == 0; lambdas are taught in Lambdas and Functional Interfaces.

Java

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

public class RemoveIf {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= 12; i++) nums.add(i);

        boolean changed = nums.removeIf(n -> n % 3 == 0);
        System.out.println(changed + " " + nums);

        List<Integer> other = new ArrayList<>(List.of(1, 2, 4, 99));
        other.retainAll(nums);                  // keep only elements also in nums
        System.out.println(other);

        nums.subList(0, 4).clear();             // range removal through a view
        System.out.println(nums);

        // The Integer vs int overload trap.
        List<Integer> xs = new ArrayList<>(List.of(10, 20, 30));
        xs.remove(1);                           // remove(int index)
        xs.remove(Integer.valueOf(10));         // remove(Object)
        System.out.println(xs);
    }
}

Output

true [1, 2, 4, 5, 7, 8, 10, 11]
[1, 2, 4]
[7, 8, 10, 11]
[30]

subList returns a view backed by the list; clearing it removes the range with one array shift. List<Integer>.remove(1) picks remove(int index), not remove(Object), because overload resolution prefers a match without boxing.

Example 6: List.of, Arrays.asList, and unmodifiable views

List.of (Java 9) returns an immutable list: every mutator throws UnsupportedOperationException, and null elements are rejected at creation and in contains. Arrays.asList returns a fixed-size list backed by the array: set works and writes through to the array, but add and remove throw. Collections.unmodifiableList returns a read-only view that still shows changes to the underlying list; List.copyOf makes an independent immutable copy.

Java

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

public class ImmutableLists {
    static void attempt(String label, Runnable r) {
        try { r.run(); System.out.println(label + ": ok"); }
        catch (RuntimeException e) { System.out.println(label + ": " + e.getClass().getSimpleName()); }
    }

    public static void main(String[] args) {
        List<String> fixed = List.of("a", "b");
        attempt("List.of add", () -> fixed.add("c"));
        attempt("List.of with null", () -> List.of("a", null));
        attempt("List.of contains(null)", () -> fixed.contains(null));

        String[] array = {"x", "y"};
        List<String> view = Arrays.asList(array);
        view.set(0, "X");
        System.out.println("array[0] = " + array[0]);
        attempt("asList add", () -> view.add("z"));

        int[] prims = {1, 2, 3};
        System.out.println("Arrays.asList(int[]).size() = " + Arrays.asList(prims).size());

        List<String> source = new ArrayList<>(List.of("p"));
        List<String> readOnly = Collections.unmodifiableList(source);
        List<String> copy = List.copyOf(source);
        source.add("q");
        System.out.println("view " + readOnly + ", copy " + copy);
    }
}

Output

List.of add: UnsupportedOperationException
List.of with null: NullPointerException
List.of contains(null): NullPointerException
array[0] = X
asList add: UnsupportedOperationException
Arrays.asList(int[]).size() = 1
view [p, q], copy [p]

Arrays.asList(int[]) returns a List<int[]> with one element, because a type argument cannot be primitive and the whole array becomes the single varargs element. The helper takes a Runnable lambda only to keep the try/catch in one place.

Example 7: sequenced collections (Java 21)

SequencedCollection (Java 21, JEP 431) gives every collection with a defined encounter order the same methods: getFirst, getLast, addFirst, addLast, removeFirst, removeLast, and reversed. Before Java 21, the last element of a List was list.get(list.size() - 1) and of a LinkedHashSet required iterating. reversed() returns a view, not a copy.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.SequencedCollection;

public class Sequenced {
    static String ends(SequencedCollection<String> c) {
        return c.getFirst() + ".." + c.getLast();
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("b", "c"));
        list.addFirst("a");
        list.addLast("d");
        System.out.println(list + " " + ends(list));

        List<String> rev = list.reversed();
        list.add("e");
        System.out.println("reversed view: " + rev);

        LinkedHashSet<String> set = new LinkedHashSet<>(List.of("x", "y", "z"));
        set.addFirst("z");                      // moves z to the front
        System.out.println(set + " " + ends(set));

        ArrayDeque<String> dq = new ArrayDeque<>(List.of("1", "2"));
        System.out.println(ends(dq) + " removed " + dq.removeLast());

        try {
            List.of("k").addFirst("j");
        } catch (UnsupportedOperationException e) {
            System.out.println("immutable list: UnsupportedOperationException");
        }
    }
}

Output

[a, b, c, d] a..d
reversed view: [e, d, c, b, a]
[z, x, y] z..y
1..2 removed 2
immutable list: UnsupportedOperationException

One method signature, ends(SequencedCollection<String>), accepts a list, a linked set, and a deque. LinkedHashSet.addFirst moves an existing element instead of adding a duplicate. On an empty collection, getFirst throws NoSuchElementException.

Interview points

ArrayList grows to 10 on first add, then by half its capacity; adds are amortized O(1), get is O(1), middle insert is O(n) array shift.
LinkedList.get(i) is O(n); each element is a separate node object. ArrayDeque is the usual replacement for stacks and queues.
ArrayDeque is a circular array that rejects null; Stack is a legacy synchronized class.
Fail-fast iterators compare modCount and throw ConcurrentModificationException; it is best effort, single-thread misuse detection, not a concurrency guarantee.
Remove during iteration with Iterator.remove or removeIf, never with list.remove inside a for-each loop.
List.of is immutable and null-hostile; Arrays.asList is fixed-size and writes through; unmodifiableList is a view; List.copyOf is a copy.
list.remove(1) on a List<Integer> removes by index.
Java 21 sequenced collections add getFirst, getLast, addFirst, reversed to lists, deques, linked sets, and sorted sets.

Summary

Collection splits into List, Set, and Queue/Deque; Java 21 inserted SequencedCollection above ordered ones.
ensureCapacity and the capacity constructor avoid repeated grows; trimToSize releases slack.
ArrayDeque grows by capacity + 2 below 64 and by half above.
Structural modification increments modCount; iterators check it in next.
Immutable lists throw UnsupportedOperationException on every mutator, including addFirst.