SyntaxPilot
Courses/Java/Lesson 30

Java · Lesson 30 of 51 · 11 min

Collections 1: ArrayList, LinkedList, Iterator

queued

These are the notes for Java episode 30, the start of the Collections series. A train's waiting list keeps growing, but an array can't. Copying into a bigger array by hand works but is error-prone, so we invent ArrayList, a class that grows itself. Then inserting at the front gets slow, so we invent LinkedList, a chain of nodes. We race the two with real timings, meet the Collections framework (Collection, List), and fix the crash you get when removing items while looping with the Iterator. Every example was run with javac 21.

The problem: an array can't grow

The waiting list chart has three lines: Asha, Ravi and Meena. Then Kabir books.

public class Main {
    public static void main(String[] args) {
        String[] waiting = new String[3];
        waiting[0] = "Asha";
        waiting[1] = "Ravi";
        waiting[2] = "Meena";
        waiting[3] = "Kabir";       // a 4th passenger
        System.out.println("Waiting: " + waiting.length);
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
    at Main.main(Main.java:7)

An array's size is fixed when it's created (episode 7): Java reserves exactly that many slots side by side in memory.

Obvious fix: copy into a bigger array

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] waiting = { "Asha", "Ravi", "Meena" };
        int count = 3;
        // a 4th passenger: make a bigger array and copy everything
        if (count == waiting.length) {
            waiting = Arrays.copyOf(waiting, waiting.length * 2);
        }
        waiting[count++] = "Kabir";
        System.out.println(Arrays.toString(waiting) + " count=" + count);
    }
}
[Asha, Ravi, Meena, Kabir, null, null] count=4

It works, but every program would have to track count, check if full, copy, and never read past count. One forgotten check is a crash.

The fix: ArrayList

At the booking office In Java
A smart clerk: you just say "add Kabir" ArrayList: a class around an array
Chart full? A new chart, about 1.5 times bigger grows itself by copying into a bigger array
Jump straight to line WL 2 get(i) is instant, like an array

An ArrayList is a dynamic array: an array wrapped in a class that grows it for you. Its capacity (the size of the hidden array) starts at 10 and grows by about 1.5x when full; its size is the number of items you've actually added.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> waiting = new ArrayList<>();
        waiting.add("Asha");
        waiting.add("Ravi");
        waiting.add("Meena");
        waiting.add("Kabir");            // just grows
        waiting.add(1, "Neha");          // insert at index 1
        System.out.println(waiting + " size=" + waiting.size());
        System.out.println(waiting.get(2) + " " + waiting.contains("Kabir"));
        System.out.println(waiting.indexOf("Meena"));
        waiting.set(0, "Asha K");
        waiting.remove("Ravi");
        System.out.println(waiting);
    }
}
[Asha, Neha, Ravi, Meena, Kabir] size=5
Ravi true
3
[Asha K, Neha, Meena, Kabir]
Method Does Example result
add(x) adds at the end
add(i, x) inserts at index i, shifts the rest Neha at 1
get(i) item at index i get(2) → Ravi
set(i, x) replaces item i
remove(i) / remove(obj) removes by index / by value
size() number of items (not length) 5
contains(x) / indexOf(x) is it there? / where? (-1 if absent) true / 3
isEmpty(), clear() empty check / remove all

Printing a list shows [a, b, c] thanks to its toString() (episode 22).

The remove trap

List<Integer> seats = new ArrayList<>(List.of(10, 20, 30));
seats.remove(10);      // remove the seat number 10?
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 10 out of bounds for length 3
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)
    ...
    at java.base/java.util.ArrayList.remove(ArrayList.java:551)
    at Main.main(Main.java:7)

There are two remove methods. 10 is an int, so Java picks remove(int index). To remove the value, box it (episode 28):

seats.remove(1);                      // index 1
System.out.println(seats);
seats.remove(Integer.valueOf(10));    // the value 10
System.out.println(seats);
[10, 30]
[30]

Inserting at the front is slow on an ArrayList

VIP and senior-citizen passengers jump to the front: add(0, x), 100,000 times.

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

public class Main {
    static long addFront(List<Integer> list) {
        long t = System.nanoTime();
        for (int i = 0; i < 100_000; i++) list.add(0, i);
        return (System.nanoTime() - t) / 1_000_000;
    }

    public static void main(String[] args) {
        System.out.println("ArrayList:  " + addFront(new ArrayList<>()) + " ms");
        System.out.println("LinkedList: " + addFront(new LinkedList<>()) + " ms");
    }
}

One run on our machine (times vary):

ArrayList:  442 ms
LinkedList: 23 ms

To put an item at index 0 of an array, every other item must shift one place.

LinkedList: a chain of nodes

A train In Java
Each coach holds passengers a node holds one item
Couplings hook each coach to the next each node has next and prev references
Add a coach at the front: change one coupling addFirst: nothing shifts
Find coach 7: walk from the engine get(i) walks the chain

Java's LinkedList is a doubly linked list: each node points to the next and the previous node, and the list remembers the first and last node.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> waiting = new LinkedList<>();
        waiting.add("Ravi");
        waiting.addFirst("Asha");     // VIP at the front
        waiting.addLast("Meena");
        System.out.println(waiting);
        System.out.println(waiting.getFirst() + " " + waiting.getLast());
        waiting.removeFirst();        // Asha got a seat
        System.out.println(waiting);
    }
}
[Asha, Ravi, Meena]
Asha Meena
[Ravi, Meena]

But get(i) is slow on a LinkedList

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

public class Main {
    static long readAll(List<Integer> list) {
        for (int i = 0; i < 50_000; i++) list.add(i);
        long t = System.nanoTime(), sum = 0;
        for (int i = 0; i < list.size(); i++) sum += list.get(i);
        return (System.nanoTime() - t) / 1_000_000;
    }

    public static void main(String[] args) {
        System.out.println("ArrayList:  " + readAll(new ArrayList<>()) + " ms");
        System.out.println("LinkedList: " + readAll(new LinkedList<>()) + " ms");
    }
}

One run on our machine:

ArrayList:  5 ms
LinkedList: 1211 ms

Every get(i) walks from the nearer end. Never use get(i) in a loop on a LinkedList; a for-each loop walks it once.

ArrayList vs LinkedList

Operation ArrayList LinkedList
get(i), set(i) O(1), instant O(n), walks the chain
add at the end O(1) on average (sometimes copies) O(1)
add/remove at the front O(n), shifts everything O(1)
add/remove in the middle (by index) O(n), shifts O(n) to walk there, then O(1)
memory compact array one node object per item
use it for almost everything (the default) work at both ends (a queue)

O(1) means "about the same time at any size"; O(n) means "time grows with the number of items" (Big-O, episode 47). For queues, ArrayDeque (episode 33) is usually better than LinkedList.

The Collections framework

  • Collection (interface): the top: add, remove, size, contains, isEmpty, iteration.
  • List (interface, extends Collection): ordered, by index, duplicates allowed.
  • ArrayList, LinkedList: classes that implement List.
  • Coming next: Set (episode 31), Map (episode 32), Queue/Deque (episode 33).

Program to the interface:

List<String> waiting = new ArrayList<>();   // switch to new LinkedList<>() in one place

Removing while looping: ConcurrentModificationException

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

public class Main {
    public static void main(String[] args) {
        List<String> waiting = new ArrayList<>(List.of("Asha", "Ravi", "Meena", "Kabir"));
        for (String p : waiting) {
            if (p.startsWith("R") || p.startsWith("M")) waiting.remove(p);   // cancelled
        }
        System.out.println(waiting);
    }
}
Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
    at Main.main(Main.java:7)

A for-each loop uses a hidden iterator. Changing the list behind its back would shift positions under it, so Java fails fast instead of silently skipping items.

The Iterator

On the train In Java
The TTE walks the chart Iterator: a walker for a collection
Anyone left? hasNext()
Next passenger next()
The TTE strikes a name himself it.remove(): safe removal
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> waiting = new ArrayList<>(List.of("Asha", "Ravi", "Meena", "Kabir"));
        Iterator<String> it = waiting.iterator();
        while (it.hasNext()) {
            String p = it.next();
            if (p.startsWith("R") || p.startsWith("M")) it.remove();   // safe
        }
        System.out.println(waiting);
        waiting.removeIf(p -> p.startsWith("K"));
        System.out.println(waiting);
    }
}
[Asha, Kabir]
[Asha]

removeIf takes a rule written as a lambda (p -> ..., episode 36).

List.of is read-only

List<String> coaches = List.of("S1", "S2", "B1");
System.out.println(coaches);
coaches.add("A1");
[S1, S2, B1]
Exception in thread "main" java.lang.UnsupportedOperationException
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
    ...

To edit, copy it: new ArrayList<>(List.of(...)).

Common mistakes (and the real error messages)

Mistake Real message Why Fix
waiting[3] = "Kabir"; on a String[3] ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3 arrays can't grow ArrayList<String>
seats.remove(10) on a List<Integer> meaning the value IndexOutOfBoundsException: Index 10 out of bounds for length 3 remove(int) is by index remove(Integer.valueOf(10))
list.remove(x) inside for-each java.util.ConcurrentModificationException changed while iterating it.remove() or removeIf
List.of(...).add(x) java.lang.UnsupportedOperationException List.of is immutable new ArrayList<>(List.of(...))
list.length error: cannot find symbol / symbol: variable length lists use a method list.size()
get(i) in a loop on a LinkedList no error, very slow walks the chain each time for-each loop

Mini project: the waiting-list desk

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

public class Main {
    public static void main(String[] args) {
        List<String> confirmed = new ArrayList<>();
        LinkedList<String> waiting = new LinkedList<>(List.of("Asha", "Ravi", "Meena", "Kabir", "Neha"));
        waiting.addFirst("Mr. Rao (senior)");          // senior citizen quota

        // 2 seats free up: the front of the waiting list gets them
        for (int seat = 0; seat < 2; seat++) confirmed.add(waiting.removeFirst());

        // Meena cancels
        Iterator<String> it = waiting.iterator();
        while (it.hasNext()) if (it.next().equals("Meena")) it.remove();

        System.out.println("Confirmed: " + confirmed);
        int wl = 1;
        for (String p : waiting) System.out.println("WL " + (wl++) + ": " + p);
    }
}
Confirmed: [Mr. Rao (senior), Asha]
WL 1: Ravi
WL 2: Kabir
WL 3: Neha

Practice

  1. Store 5 passengers in an ArrayList; print who is at index 2.
  2. Remove every even number from a List<Integer> safely.
  3. Time add at the end 100,000 times for both lists. Who wins?
  4. Reverse a LinkedList by addFirst-ing each item into a new list.
Solutions

1. list.get(2).

2.

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
nums.removeIf(n -> n % 2 == 0);
System.out.println(nums);   // [1, 3, 5]

(or an Iterator with it.remove()).

3. Both are fast (O(1) each); ArrayList is usually a little faster because it doesn't create a node object per item.

4.

LinkedList<String> src = new LinkedList<>(List.of("A", "B", "C"));
LinkedList<String> rev = new LinkedList<>();
for (String x : src) rev.addFirst(x);
System.out.println(rev);   // [C, B, A]

Quick quiz

List<Integer> list = new ArrayList<>(List.of(5, 1, 7));
list.add(1, 9);
list.remove(2);
list.remove(Integer.valueOf(7));
System.out.println(list);

A) [5, 9] B) [5, 1] C) [9, 1] D) IndexOutOfBoundsException

Answer

A. add(1, 9) → [5, 9, 1, 7]. remove(2) removes index 2 (the 1) → [5, 9, 7]. remove(Integer.valueOf(7)) removes the value 7 → [5, 9].

Interview questions

  1. ArrayList vs LinkedList? Dynamic array (fast random access, slow front inserts) vs doubly linked list (fast at the ends, slow random access). ArrayList is the default.
  2. How does ArrayList grow? When full, it allocates a new array about 1.5x larger and copies the elements (amortised O(1) add).
  3. Size vs capacity? Size = items stored; capacity = length of the internal array.
  4. What is ConcurrentModificationException? Thrown when a collection is structurally changed while being iterated, except through the iterator itself.
  5. How do you remove items while iterating? Iterator.remove() or removeIf.
  6. remove(int) vs remove(Object) on List<Integer>? By index vs by value; box the value to remove by value.
  7. What does List.of return? An immutable list; add/remove throw UnsupportedOperationException, and it doesn't allow null.
  8. Why declare List<T> x = new ArrayList<>()? Programming to the interface keeps code flexible.

Glossary

Term Meaning Example
Collection An object that holds a group of objects; also the top interface Collection<String>
Collections framework Java's family of collection interfaces and classes List, Set, Map, Queue
List Ordered collection, by index, duplicates allowed List<String>
ArrayList A dynamic array that grows itself new ArrayList<>()
Dynamic array An array that is replaced by a bigger copy when full ArrayList inside
Capacity Length of the hidden array starts at 10
Size Number of items stored list.size()
LinkedList A chain of nodes linked both ways new LinkedList<>()
Node One link of the chain: an item plus references next, prev
Doubly linked list Each node knows the next and previous node Java's LinkedList
Iterator An object that walks a collection one item at a time list.iterator()
hasNext / next Are there more items? / give me the next one while (it.hasNext())
ConcurrentModificationException Collection changed during iteration remove in for-each
Immutable list A list that can't be changed List.of(...)
UnsupportedOperationException The operation isn't allowed on this object List.of(...).add(x)
Program to the interface Declare variables with the interface type List<T> x = new ArrayList<>()
O(1) / O(n) Constant time / time that grows with n get(i) / add(0, x)
Arrays.copyOf Copies an array into a new one of a given length Arrays.copyOf(a, 6)

Summary

  • Arrays have a fixed size; copying by hand is error-prone.
  • ArrayList wraps an array and grows it for you: fast get/set, slow inserts at the front.
  • remove(int) removes by index; use remove(Integer.valueOf(x)) for the value.
  • LinkedList is a chain of nodes: fast at both ends, slow get(i).
  • Both implement List; declare variables as List and pick the class on the right.
  • Removing in a for-each throws ConcurrentModificationException; use the Iterator's remove() or removeIf.
  • List.of is read-only.
  • Next: collections that refuse duplicates: HashSet, LinkedHashSet, TreeSet (episode 31).