10.2 List Costs, Views, and Updates

This is the second stop after getting familiar with the collection framework. By running the Java 17 examples in about 35 minutes, you'll gain insight into the implementation cost of List, the difference between views and copies, and how to safely delete or modify elements while iterating.

Choose the Implementation by Its Operation Pattern

Material requests need ordered appends, positional reads, and repeated requests by the same person. These actions fit List semantics: preserving the order of encounters, allowing duplicates, and supporting positional access. The implementation choice also depends on the distribution of actions. When most records are appended to the end and accessed by index, an ArrayList backed by an array of references is appropriate. If the List is treated as a double-ended queue, although LinkedList can work, ArrayDeque often expresses the intent more accurately. It implements Deque, not List, so the variable interface must change too.

1. ArrayList Manages a Growing Reference Array

List<String> claims = new ArrayList<>();
claims.add("Material Requisition Form-1");
claims.add("Material Requisition Form-2");
claims.add(0, "Urgent order");

The observable contract of ArrayList includes:

• get(index) and set(index, value) are O(1);
• Tail add(value) is amortized O(1);
• Insertion or deletion in the middle requires moving subsequent references, which is O(n);
• indexOf and contains are linearly searched using equals, which is O(n).

When the internal array is filled, the JDK allocates more storage and copies the elements. The growth formula, when the empty list is first allocated, and the internal fields are all implementation details. The Java API does not guarantee a fixed growth of 1.5 times. Application code should rely on amortized complexity rather than a specific JDK source code constant.

When the size is known, a capacity estimate can be provided to the constructor:

List<Order> orders = new ArrayList<>(expectedCount);

Capacity is not size. new ArrayList<>(1000) only reserves storage space, size() is still 0; it cannot guarantee "zero expansion" from the interface level, because the actual number of elements may exceed the estimate. When holding a specific ArrayList type, you can also call ensureCapacity, but it is usually not necessary to expose the implementation type to the caller for capacity.

2. O(1) Operations with Positional Constraints for LinkedList

LinkedList maintains a predecessor and successor link for each element:

Deque<String> waiting = new LinkedList<>();
waiting.addFirst("Zhang San");
waiting.addLast("Li Si");

When the head and tail nodes are known, inserting and deleting at the ends is O(1). list.add(index, value) still has to locate the index first, which costs O(n). Simply "frequent middle insertions" are not enough to justify using LinkedList; only when you already hold ListIterator and are continuously modifying at the current position can you avoid repeated lookups.

LinkedList nodes also store links, which are less friendly to CPU cache than contiguous arrays. Real performance depends on data size and access patterns, so it's not appropriate to reference a fixed number of milliseconds. When comparisons are needed, use JMH to account for warm-up, dead-code elimination, and timing noise.

Operation	ArrayList	LinkedList
get(i) / set(i, e)	O(1)	O(n)
Tail Append	Amortized O(1)	O(1)
add(0, e)	O(n)	O(1)
add(i, e)	O(n) Move	O(n) Locate, Then O(1) Link
indexOf(e)	O(n)	O(n)
Delete When Iterator Is at Current Position	O(n) Move	O(1) Link

When FIFO/LIFO or two-end operations are needed, prefer ArrayDeque. It does not support index-based access and does not allow null, which is exactly what makes poll return null to indicate an empty queue.

3. Overloading remove Can Change Meaning

The easiest place to mistakenly delete is on List<Integer>:

List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));

numbers.remove(1);                 // Call remove(int index), Delete 20
numbers.remove(Integer.valueOf(30)); // Call remove(Object), Remove value 30

remove(index) returns the deleted element; remove(object) returns whether an element was found and deleted. When you see an integer parameter, first confirm whether you need the position or the value.

4. Three Objects That "Look Like" a List

Arrays.asList: Fixed-Size View of an Array

String[] array = {"Component", "Wood"};
List<String> view = Arrays.asList(array);

view.set(0, "Steel component");   // array[0] Also becomes“Steel component”
// view.add("Leather");   // UnsupportedOperationException

It allows set but not resizing; the array and list share element storage. A primitive array adds another trap: Arrays.asList does not turn int[] into individual Integer elements. It treats the entire array as one element:

int[] values = {1, 2, 3};
List<int[]> oneArray = Arrays.asList(values);
System.out.println(oneArray.size()); // 1

For List<Integer>, use Arrays.stream(values).boxed().toList(). That result is still unmodifiable.

List.of: An Unmodifiable List

List<String> fixed = List.of("Component", "Wood");

It rejects add, remove, and set, and also rejects null elements. The implementation type is not part of the contract.

new ArrayList<>(source): Independent Mutable Copy

List<String> copy = new ArrayList<>(fixed);
copy.add("Leather");

This is a shallow copy: the list structure is independent, but the element objects are still shared. When the elements themselves are mutable, you must decide whether to also copy the elements.

5. subList is a Range View Backed by the Original List

List<String> ledger = new ArrayList<>(
        List.of("Component", "Wood", "Leather", "Thick rope"));
List<String> firstTwo = ledger.subList(0, 2);

firstTwo.set(1, "Hardwood");
System.out.println(ledger); // [Component, Hardwood, Leather, Thick rope]

Modifications to the view are reflected in the original list. When the original list is structurally modified outside the view, continuing to use the old subList often fails a concurrent-modification check; the API does not provide general guarantees for such scenarios.

When an independent result is needed, copy:

List<String> snapshot = List.copyOf(ledger.subList(0, 2));

List.copyOf returns an unmodifiable shallow copy and rejects null. For a mutable copy, use new ArrayList<>(...).

6. Deleting from the Original List During Iteration

The legacy code was written as:

for (String item : items) {
    if (item.startsWith("Void")) {
        items.remove(item);
    }
}

Enhanced for loops use Iterator. ArrayList and similar implementations maintain a structure modification count; when an Iterator detects a discrepancy between the expected count and the actual count, it often throws ConcurrentModificationException. Fail-fast is a mechanism designed to detect program errors as best as possible, but it does not guarantee that it will throw an exception in every timing scenario, and it cannot replace synchronization.

Deleting Based on a Condition: removeIf

items.removeIf(item -> item.startsWith("Void"));

Need for More Control During Iteration: Iterator.remove

Iterator<String> iterator = items.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.startsWith("Void")) {
        iterator.remove();
    }
}

It must first successfully call next, and after each next, the remove can be called at most once. Specific List implementations may return Iterators that do not support deletion, such as unmodifiable lists.

Need to Process by Position: Reverse Indexing

for (int index = items.size() - 1; index >= 0; index--) {
    if (items.get(index).startsWith("Void")) {
        items.remove(index);
    }
}

Reverse indexing can avoid the problem of skipped elements caused by leftward shifting of unaccessed elements after deletion. ArrayList still requires element movement for each intermediate deletion, and bulk conditional deletions are usually better expressed with removeIf.

7. ListIterator Supporting Bidirectional and In-Place Editing

ListIterator<String> iterator = items.listIterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.equals("Wood")) iterator.set("Hardwood");
    if (item.equals("Component")) iterator.add("Quality inspection record");
}

Set replaces the element most recently returned by next or previous. Add inserts before the cursor and leaves the cursor after the new element, so the next call to next skips it. After add or remove, set is invalid until another successful next or previous call. When batch mapping all elements is required, replaceAll is often more concise.

8. Complete Working Example

First, prepare a temporary directory:

chapter10_list_root=$(mktemp -d)
readonly chapter10_list_root
mkdir -p "$chapter10_list_root/out"
cd "$chapter10_list_root"

Save as ListContractsDemo.java:

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

public class ListContractsDemo {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>(
                List.of("Component", "Void-Wood", "Leather", "Void-Thick rope"));
        items.removeIf(item -> item.startsWith("Void"));
        checkEquals(List.of("Component", "Leather"), items);

        items.addAll(List.of("Void-Old material", "Hardwood"));
        Iterator<String> iterator = items.iterator();
        while (iterator.hasNext()) {
            if (iterator.next().startsWith("Void")) iterator.remove();
        }
        checkEquals(List.of("Component", "Leather", "Hardwood"), items);

        List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));
        checkEquals(20, numbers.remove(1));
        check(numbers.remove(Integer.valueOf(30)), "Delete by value 30");
        checkEquals(List.of(10), numbers);

        String[] array = {"Component", "Wood"};
        List<String> arrayView = Arrays.asList(array);
        arrayView.set(0, "Steel component");
        checkEquals("Steel component", array[0]);
        expect(UnsupportedOperationException.class,
                () -> arrayView.add("Leather"));

        List<String> ledger = new ArrayList<>(
                List.of("Component", "Wood", "Leather"));
        List<String> view = ledger.subList(0, 2);
        view.set(1, "Hardwood");
        checkEquals(List.of("Component", "Hardwood", "Leather"), ledger);

        Iterator<String> stale = ledger.iterator();
        ledger.add("Thick rope");
        expect(ConcurrentModificationException.class, stale::next);

        List<String> snapshot = List.copyOf(ledger.subList(0, 2));
        ledger.set(0, "Steel component");
        checkEquals(List.of("Component", "Hardwood"), snapshot);
        expect(UnsupportedOperationException.class,
                () -> snapshot.add("New material"));

        System.out.println("Valid material requests: " + items);
        System.out.println("Array view: " + arrayView);
        System.out.println("Independent snapshot: " + snapshot);
        System.out.println("List contract check passed");
    }

    static void expect(Class<? extends Throwable> type, Runnable action) {
        try {
            action.run();
        } catch (Throwable throwable) {
            if (type.isInstance(throwable)) return;
            throw new AssertionError(
                    "expected=" + type + ", actual=" + throwable, throwable);
        }
        throw new AssertionError("expected exception=" + type.getName());
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void checkEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("expected=" + expected + ", actual=" + actual);
        }
    }
}

Run:

javac --release 17 -encoding UTF-8 -Xlint:all -d out ListContractsDemo.java
java -cp out ListContractsDemo

Expected output:

Valid material requests: [Component, Leather, Hardwood]
Array view: [Steel component, Wood]
Independent snapshot: [Component, Hardwood]
List contract check passed

Save the required output and clean up:

cd
ls -ld -- "$chapter10_list_root"
rm -r -- "$chapter10_list_root"

Before Closing the Ledger, Confirm Where Modifications Are Sent

When you encounter a List, don't rush to call add or remove. Determine whether it's an independent ArrayList, a fixed-size view of an array, a subList of the original list, or an unmodifiable snapshot. Then assess whether the elements are shared. As long as this chain of ownership can be clarified, many unexpected issues that seem to be "List" will disappear.

Then use the example in this section to make a small change: respectively delete all obsolete records using removeIf, the current Iterator, and reverse indexing, and verify that no items are missed. If an integer is passed to remove, clearly determine whether it represents an index or an element value.

Reviewing the Official Contract for Java 17

• List: Indexes, optional operations, subList and modification constraints.
• ArrayList, LinkedList and ArrayDeque: Implementation cost and applicable operations.
• Arrays.asList, List.of and List.copyOf: Fixed-size views, unmodifiable lists, and snapshots.
• Iterator and ListIterator: State constraints during traversal.

Next Step: Indexing Inventory

The next lesson maps material names to stock quantities and examines how equality rules affect Set deduplication.

Continue learning about Map and Set