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, extendsCollection): ordered, by index, duplicates allowed.ArrayList,LinkedList: classes that implementList.- 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
- Store 5 passengers in an
ArrayList; print who is at index 2. - Remove every even number from a
List<Integer>safely. - Time
addat the end 100,000 times for both lists. Who wins? - Reverse a
LinkedListbyaddFirst-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
- 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.
- How does ArrayList grow? When full, it allocates a new array about 1.5x larger and copies the elements (amortised O(1) add).
- Size vs capacity? Size = items stored; capacity = length of the internal array.
- What is ConcurrentModificationException? Thrown when a collection is structurally changed while being iterated, except through the iterator itself.
- How do you remove items while iterating?
Iterator.remove()orremoveIf. remove(int)vsremove(Object)onList<Integer>? By index vs by value; box the value to remove by value.- What does
List.ofreturn? An immutable list;add/removethrowUnsupportedOperationException, and it doesn't allownull. - 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; useremove(Integer.valueOf(x))for the value.- LinkedList is a chain of nodes: fast at both ends, slow
get(i). - Both implement
List; declare variables asListand pick the class on the right. - Removing in a for-each throws ConcurrentModificationException; use the Iterator's
remove()orremoveIf. List.ofis read-only.- Next: collections that refuse duplicates: HashSet, LinkedHashSet, TreeSet (episode 31).