Core Libraries

The Collections Framework

Program to an interface (List), not an implementation you marry (ArrayList or LinkedList). A List grows where an array can't, and it holds Integer, not int, which brings autoboxing and the remove(int) trap. The Iterator behind for-each forbids changing the list mid-loop. Also covers sorting (natural order, Comparable, reverse and case-insensitive), the Deque as a stack and a queue, and choosing an implementation. Every behavior is shown with verified output.

Suggest an edit

The Collections Framework — Program to the Interface

Arrays were our first containers, but their fixed size is a real limit. The Collections Framework is Java's library of growable, feature-rich containers. Its central design idea is worth more than any single class in it:

  • you program to an interface (List), a named set of operations;
  • you choose an implementation (ArrayList, LinkedList) only at the moment you create the object.

Code written against List works with any list, so you can swap implementations for performance without changing a single line that uses them. This lesson covers List and why it holds Integer instead of int. After that come the Iterator behind every for-each, sorting, the Deque as a stack and a queue, and how to choose an implementation.

💡 The core idea.

  • Program to the interface (List), not the implementation (ArrayList/LinkedList).
  • Declaring the interface lets you swap implementations freely.
  • Collections hold objects, so an int travels as an Integer.
  • The Iterator drives for-each and forbids modifying mid-loop.
  • Implementation choice is a performance trade-off, not a correctness one.

This is the deep pass of arrays. The <Integer> notation is a generic type, "a List of Integer". It gets its full treatment in Generics. For now, read it as "this list holds Integers". Every output below was produced by compiling and running the code on Java 25.

You'll be able to: add, read, replace and remove elements of a List, and predict what a List.of list allows; explain why a list holds Integer, not int, and predict what remove(1) removes from a List<Integer>; predict when changing a list inside a for-each throws, and remove safely with an Iterator; sort a list in natural, reverse and case-insensitive order, and make a class of your own sortable; use a Deque as a stack and as a queue, and pick between ArrayList, LinkedList and ArrayDeque.

📘 How to read the Intuition boxes. Each one is built in three moves:

  1. The mechanism — what the compiler and the JVM do.
  2. A concrete bite — a specific, runnable failure (often a real compiler error), shown so the trap is visible.
  3. The earned rule — the decision heuristic, now justified rather than asserted, plus its cost.

Table of contents

  1. A List grows where an array can't
  2. Integer, not int: wrappers in collections
  3. Program to the interface
  4. Iteration, the Iterator, and the modification trap
  5. Sorting a list
  6. Deque: a stack and a queue
  7. Choosing an implementation
  8. Mental-model summary
  9. Gotcha checklist
  10. Check yourself
  11. Sources

1. A List grows where an array can't

A List is an ordered, resizable sequence [1]:

  • add appends;
  • get(i) reads by index;
  • set(i, v) replaces;
  • size() reports the count.

Unlike an array, it grows as you add.

Output:

3
85
[90, 100, 95]

Analysis. We never declared a size. add grew the list to three.

  • get(1) returned the element at index 1 (85). Indices start at 0, just as with arrays.
  • set(1, 100) replaced it.
  • Printing the list shows [90, 100, 95]. A List has a readable toString, unlike a bare array.

The empty <> after ArrayList is the diamond form [19], and the compiler fills in Integer from the variable's type.

Intuition. Mechanism. ArrayList keeps its elements in an array. When the array fills, it allocates a bigger one and copies the elements over. The API leaves the growth policy unspecified "beyond the fact that adding an element has constant amortized time cost" [2]. Underneath, get and set are direct array indexing.

Concrete bite. Not every List grows. List.of(...) builds an unmodifiable list, and any add, remove or set throws [1]:

Output (prints one line, then a thrown exception):

[a, b]
Exception in thread "main" java.lang.UnsupportedOperationException

List.of is handy for a fixed list of values. To get a list you can change, copy it into an ArrayList: new ArrayList<>(List.of("a", "b")) accepts add("c") and prints [a, b, c].

💡 Earned rule. Reach for a List whenever the number of elements isn't fixed up front, which is most of the time. Keep a bare array only when the size is truly fixed and you need raw speed or primitives without boxing. Use List.of for values that never change, and new ArrayList<>(…) for a list you'll edit.

A List costs you the boxing of primitives (next section) and a little overhead per element. The payoff is growth, a rich API, and a real toString.

2. Integer, not int: wrappers in collections

A collection holds objects, never primitives. The type inside <…> must be a reference type [3], so List<int> doesn't compile:

Compiler error:

Main.java:6: error: unexpected type
        List<int> nums = new ArrayList<>();
             ^
  required: reference
  found:    int

The fix is the wrapper class from References, Equality & the Object Model: List<Integer>. Java converts in both directions for you:

  • boxing wraps an int into an Integer when you add it [4];
  • unboxing unwraps an Integer into an int when you assign it to an int [5].

A list of Integer can also hold null, which no int can. Unbox that null, and it throws:

Output (prints two lines, then a thrown exception):

8
[7, null]
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Iterator.next()" is null

Analysis. add(7) boxed and get(0) unboxed, so first + 1 is 8. The list printed null without complaint. The crash came in the loop, because for (int n : nums) unboxes each element into int n, and the second element was null. The message names Iterator.next(), your first glimpse of the machinery in §4.

Intuition. Mechanism. Boxing is automatic, and so is its failure. A List method may take either an index (int) or an element (Object), and List declares both versions: remove(int index) and remove(Object o) [1]. The compiler first looks for a method that fits without boxing [6]. With an int argument, remove(int) fits, so it wins.

Concrete bite. remove(1) on a List<Integer> removes the element at index 1, not the value 1:

Output:

[10, 30]
[30]

Analysis. remove(1) did not remove a value 1. It removed the element at index 1 (the 20), leaving [10, 30]. To remove by value, pass an Integer object, as remove(Integer.valueOf(10)) did to remove the value 10.

💡 Earned rule. Write List<Integer>, and let boxing do the conversions. With a List<Integer>, remove by value with remove(Integer.valueOf(x)) or remove((Integer) x), never a bare remove(x), which means index. Keep null out of a list you'll unbox.

The cost is one object per number and one overload to remember. The payoff is every collection in the library, for numbers too.

3. Program to the interface

List is an interface, a contract of operations. ArrayList and LinkedList are two implementations of it. Declare your variables and parameters as List, and your code works with any implementation. The concrete class shows up only at new.

Output:

6
30

Analysis. sum is written against List, so it summed both an ArrayList and a LinkedList with no change, because they share the List contract. The diagram shows the relationship:

  • List extends Collection, the root interface of the framework [7];
  • both concrete classes implement List (the dotted lines).

The variable type (List) is the contract, and the new type is the implementation.

Intuition. Mechanism. The compiler checks a call on a List variable against List's declared methods only. So any object whose class implements List will do. At run time, the actual implementation's methods run. Inheritance & Polymorphism calls this dynamic dispatch. Your code depends on the interface, not the class.

Concrete bite. The payoff is swap-ability. Change new ArrayList<>() to new LinkedList<>(), and nothing else breaks, because every caller spoke to List. Declare the variable as ArrayList instead, and the choice is welded in. Callers can now use ArrayList-only methods, and swapping becomes a refactor.

💡 Earned rule. Declare variables, parameters, and return types with the interface (List, Collection), and name the implementation only at construction.

The cost is giving up implementation-specific methods, which you rarely need. The payoff is that the implementation becomes a decision you can revisit for performance without touching the code that uses it.

4. Iteration, the Iterator, and the modification trap

An Iterator walks every collection. It's an object with hasNext() and next() [8]. The enhanced for over a collection is shorthand for a loop over its iterator [9]. That iterator enforces a rule: you may not structurally modify a collection while a for-each is walking it.

Output:

1 2 3 4

Analysis. The for-each obtained an Iterator from nums and called hasNext() and next() under the hood to visit each element. There's no index. The iterator tracks the position.

Intuition. Mechanism. The list counts its structural changes. The iterator remembers the count it started with and checks it on each next().

Suppose something other than the iterator adds or removes an element. The counts then differ, and next() throws ConcurrentModificationException. This is called fail-fast, because it catches the bug instead of silently skipping or repeating elements [2].

Concrete bite. Remove from the list inside a for-each, and it throws:

Output (a thrown exception):

Exception in thread "main" java.util.ConcurrentModificationException

nums.remove(...) changed the list behind the for-each's iterator, so the following next() spotted the mismatch and threw. The check is only "best-effort" [2]. Remove the second-to-last element, and the loop ends before the next next(), with no exception and one element never visited:

Output:

[1, 3]

The result looks right, but the loop never visited 3, because after the removal hasNext() saw no more elements. The API warns that "it would be wrong to write a program that depended on this exception for its correctness" [2]. The fix is to remove through the iterator, whose own remove() keeps the counts in sync:

Output:

[1, 3]

💡 Earned rule. Never add or remove on a collection while a for-each is walking it, even when no exception appears. To delete during a pass, use an explicit Iterator and its remove(). Once you have lambdas, removeIf does the same in one call.

The fail-fast check costs you a for-each that can't mutate. The payoff is that most "modified mid-iteration" bugs throw loudly instead of silently corrupting the traversal.

5. Sorting a list

You sort a list in place with Collections.sort(list) or list.sort(order):

  • with no order given, elements sort by their natural ordering: numbers ascending, strings by character code [10];
  • a Comparator is an object that supplies another order. The library has ready-made ones, such as Comparator.reverseOrder() and String.CASE_INSENSITIVE_ORDER [11].

Arrays have their own Arrays.sort [12].

Output:

[10, 20, 30]
[30, 20, 10]
[Cherry, apple, banana]
[apple, banana, Cherry]
[1, 2, 5, 9]

Analysis.

  • The numbers sorted ascending, then descending with reverseOrder().
  • The natural order put Cherry first. String compares "the Unicode value of each character" [13], and the capitals A–Z come before the lowercase a–z.
  • CASE_INSENSITIVE_ORDER ignored case and gave dictionary order.
  • Arrays.sort sorted the int[] in place.

Intuition. Mechanism. Natural ordering comes from the Comparable interface. A class that implements it has a compareTo method. It returns a negative number, zero, or a positive number, meaning this is less than, equal to, or greater than the other object [10].

Integer and String implement it. A class you write doesn't, until you say so.

Concrete bite. Sort a list of your own objects, and there's no order to use:

Compiler error:

Main.java:20: error: no suitable method found for sort(List<Player>)
        Collections.sort(players);
                   ^

Collections.sort(list) accepts only a list of Comparable elements, so javac rejects it (the rest of the message is about generics). players.sort(null) compiles, but it fails at run time with ClassCastException: class Player cannot be cast to class java.lang.Comparable. The fix is to give Player a natural ordering:

Output:

[Bo=70, Cy=80, Ada=90]

Analysis.

  • implements Comparable<Player> promises that Player has a compareTo(Player) method. Interfaces get their own lesson in Abstract Classes & Interfaces.
  • Integer.compare returns the negative, zero or positive result that compareTo needs.
  • players.sort(null) means "natural order" [14], so the players sorted by score.
  • The class's own toString replaced the default Player@… text in the printout.

💡 Earned rule. Sort with list.sort(…) or Collections.sort(…). Use natural order for numbers and strings, and a Comparator for any other order. Give a class a natural ordering with Comparable when it has one obvious order.

The catch is that String's natural order isn't dictionary order: capitals sort first. For orders built on the fly, such as "by name, then by score", lambdas make a Comparator in one line.

6. Deque: a stack and a queue

A Deque ("deck", a double-ended queue) is a sequence you can add to and remove from at both ends [15]. It serves two classic shapes:

  • a stack is last-in, first-out (LIFO): push adds to the front, pop removes from the front;
  • a queue is first-in, first-out (FIFO): offer adds at the back, poll removes from the front.

peek looks at the front without removing it. ArrayDeque is the usual implementation.

Output:

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

Analysis. The stack gave back c, the last element pushed. The queue gave back a, the first element offered. Printing a deque lists it from the front.

Intuition. Mechanism. Each end has two families of methods [15]. One family throws an exception when the deque is empty: pop, removeFirst, getFirst. The other returns null: poll, peek. ArrayDeque also rejects null elements, so a null from poll always means "empty" [16].

Concrete bite. On an empty deque, poll and peek do no harm, but pop throws:

Output (prints two lines, then a thrown exception):

null
null
Exception in thread "main" java.util.NoSuchElementException

💡 Earned rule. For a stack or a queue, declare a Deque and create an ArrayDeque. Use poll and peek when empty is normal, and check for null. Use pop when empty is a bug that should throw.

You may run into the old Stack class. Its API says a Deque "should be used in preference to this class" [17].

7. Choosing an implementation

ArrayList, LinkedList and ArrayDeque differ in performance, because each stores its elements differently:

  • ArrayList uses an array;
  • LinkedList uses a chain of nodes, each linked to the next and the previous [18];
  • ArrayDeque uses a resizable array [16].

The choice is about cost, not behavior.

Operation ArrayList LinkedList ArrayDeque
get(i) / set(i) by index O(1) O(n): walk the chain not offered
add or remove at the end O(1) amortized O(1) O(1) amortized
add or remove at the front O(n): shift elements O(1) O(1) amortized
add or remove in the middle O(n): shift elements O(1) at a node you hold not offered
memory per element low (one array slot) higher (a node and two links) low (one array slot)

LinkedList "will traverse the list from the beginning or the end, whichever is closer" to reach an index [18]. That's why get(i) is O(n). ArrayDeque "is likely to be … faster than LinkedList when used as a queue" [16].

💡 Earned rule. Default to ArrayList for a list, and to ArrayDeque for a stack or a queue. Reach for LinkedList only when you insert and remove in the middle through an iterator, or need a queue that holds null.

A wrong choice costs you speed, never correctness: all three give the same results through their interfaces.

8. Mental-model summary

Principle Consequence
A List is a growable, ordered sequence No fixed size; add expands it; it has a real toString
List.of builds an unmodifiable list add, remove and set throw UnsupportedOperationException; copy into an ArrayList to edit
Collections hold objects, not primitives List<Integer>, not List<int>; boxing and unboxing convert; unboxing null throws
remove(int) and remove(Object) are overloads A bare int picks the index version
Program to the interface (List), choose the implementation at new Code works with any List; you can swap implementations freely
A for-each runs on an Iterator and is fail-fast, best-effort Modifying the collection mid-loop throws, or silently skips; delete through the iterator
Natural order comes from Comparable; other orders from a Comparator String sorts capitals first; a class of your own needs Comparable to sort by itself
A Deque is a stack (push/pop) or a queue (offer/poll) pop on empty throws; poll and peek return null
Implementation is a performance choice, same interface ArrayList for lists, ArrayDeque for stacks and queues

9. Gotcha checklist

Symptom Likely cause Fix
UnsupportedOperationException on add or remove the list came from List.of new ArrayList<>(List.of(…))
unexpected type, required: reference, found: int a primitive inside <…> List<Integer>
Cannot invoke "java.lang.Integer.intValue()" in a for-each a null element unboxed into int keep null out, or loop with Integer and check
list.remove(x) removed the wrong element remove(int) is by index remove(Integer.valueOf(x))
ConcurrentModificationException add or remove during a for-each an explicit Iterator and its remove(), or removeIf
An element was never visited after a removal in a for-each fail-fast is best-effort; removing the second-to-last ends the loop the same fix; never rely on the exception
no suitable method found for sort(List<…>) the element class is not Comparable implement Comparable, or pass a Comparator
ClassCastException: … cannot be cast to class java.lang.Comparable list.sort(null) on a class with no natural order the same fix
Sorted strings put Zebra before apple natural order compares character codes String.CASE_INSENSITIVE_ORDER
NoSuchElementException from pop the deque was empty check isEmpty(), or use poll and test for null
You declared ArrayList and now can't swap it the variable names the implementation declare it as List
Index access on a LinkedList is slow get(i) walks the chain ArrayList for index-heavy work

✅ Check yourself

One check per objective. Answer before you open anything.

The 🧪 box below: set(0, "z"), removing every "b" in a for-each, and xs.remove(1) against xs.remove(Integer.valueOf(1)).
  • After add("a"), add("b"), add("c") and set(0, "z"), the list prints [z, b, c].
  • Removing every "b" from ["a", "b", "b", "c"] inside a for-each throws ConcurrentModificationException. The first "b" removed sits at index 1, not in the second-to-last position, so the loop calls next() again and the check fires. The iterator version prints [a, c]:

Output:

[a, c]
  • xs.remove(1) on [5, 7] removes index 1 and leaves [5]. xs.remove(Integer.valueOf(1)) looks for the value 1, finds none, returns false, and leaves [5, 7] alone.

📚 Sources

  1. java.util.List, Java SE 25 API ("Unmodifiable Lists"; remove(int) and remove(Object)) — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/List.html
  2. java.util.ArrayList, Java SE 25 API (growth policy; "fail-fast … on a best-effort basis") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/ArrayList.html
  3. The Java Language Specification, Java SE 25, §4.5.1 "Type Arguments of Parameterized Types" ("Type arguments may be either reference types or wildcards") — https://docs.oracle.com/javase/specs/jls/se25/html/jls-4.html#jls-4.5.1
  4. The Java Language Specification, Java SE 25, §5.1.7 "Boxing Conversion" — https://docs.oracle.com/javase/specs/jls/se25/html/jls-5.html#jls-5.1.7
  5. The Java Language Specification, Java SE 25, §5.1.8 "Unboxing Conversion" — https://docs.oracle.com/javase/specs/jls/se25/html/jls-5.html#jls-5.1.8
  6. The Java Language Specification, Java SE 25, §15.12.2 "Compile-Time Step 2: Determine Method Signature" (the first phase permits no boxing) — https://docs.oracle.com/javase/specs/jls/se25/html/jls-15.html#jls-15.12.2
  7. java.util.Collection, Java SE 25 API ("The root interface in the collection hierarchy") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Collection.html
  8. java.util.Iterator, Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Iterator.html
  9. The Java Language Specification, Java SE 25, §14.14.2 "The enhanced for statement" (translation to an Iterator loop) — https://docs.oracle.com/javase/specs/jls/se25/html/jls-14.html#jls-14.14.2
  10. java.lang.Comparable, Java SE 25 API (natural ordering; compareTo returns "a negative integer, zero, or a positive integer") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/lang/Comparable.html
  11. java.util.Comparator.reverseOrder() and java.lang.String.CASE_INSENSITIVE_ORDER, Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Comparator.html#reverseOrder()
  12. java.util.Arrays.sort(int[]), Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)
  13. java.lang.String.compareTo(String), Java SE 25 API ("based on the Unicode value of each character") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/lang/String.html#compareTo(java.lang.String)
  14. java.util.List.sort(Comparator), Java SE 25 API ("If the specified comparator is null then … the elements' natural ordering should be used") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/List.html#sort(java.util.Comparator)
  15. java.util.Deque, Java SE 25 API (the two method families; stack and queue tables) — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Deque.html
  16. java.util.ArrayDeque, Java SE 25 API ("Null elements are prohibited"; faster than Stack and LinkedList) — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/ArrayDeque.html
  17. java.util.Stack, Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Stack.html
  18. java.util.LinkedList, Java SE 25 API ("Doubly-linked list"; index operations traverse) — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/LinkedList.html
  19. The Java Language Specification, Java SE 25, §15.9 "Class Instance Creation Expressions" (the diamond form <>) — https://docs.oracle.com/javase/specs/jls/se25/html/jls-15.html#jls-15.9

🧪 Predict, then check.

  1. Create a List<String>, add("a"), add("b"), add("c"), then set(0, "z"), and print it.
  2. Predict whether removing every "b" from ["a", "b", "b", "c"] inside a for-each throws, then rewrite it with an Iterator.
  3. For List<Integer> xs = new ArrayList<>(); xs.add(5); xs.add(7);, predict what xs.remove(1) leaves, and what xs.remove(Integer.valueOf(1)) would do instead.

Your Turn

Before you move on, check your understanding with the coach — explain the idea, apply it, weigh the trade-offs, then defend your reasoning.

Mark as readBook versionfd26460