PublishedBEG-030-L02

Lists

Lesson 2 of 9
12 min read
Beginner

On This Lesson 11 topics

Lesson Overview
Learning Objectives
Written Explanation
Examples
Backend Insight
Common Mistakes
Exercises
Mini Challenge
Summary & Next Lesson
References
Practice

Lesson Overview

The previous lesson gave you the map of the Collections Framework. This lesson goes deep on the collection you will use most: the List. A list keeps its elements in order, allows duplicates, and lets you reach any element by its position (index), starting at 0, exactly like an array, but it grows and shrinks for you.

You will learn the core methods (add, get, set, remove, size, contains, isEmpty), one famous trap with remove on a list of numbers, the difference between the two main implementations (ArrayList and LinkedList) and why ArrayList is the default, and a first warning that contains can be slow on large lists.

This lesson builds on Lesson 1 (the four kinds, interface-typed variables) and on arrays and loops from BEG-013 and BEG-015.

Learning Objectives

By the end of this lesson you will be able to:

Create a List<String> and use add, get, set, remove, size, contains, indexOf, and isEmpty.
Predict what a sequence of list operations leaves in the list.
Tell remove(int index) from remove(Object value) and avoid the List<Integer> trap.
Explain, at a high level, how ArrayList (backed by an array) and LinkedList (a chain of nodes) differ in speed for common operations.
Choose ArrayList as the default and say when LinkedList is worth a look.
Explain why contains on a big list is slow, and when that points to a Set or Map.
Create an unmodifiable list with List.of and explain why it throws when you change it.

Written Explanation

What a list promises

A List is an ordered collection. You decide where each element goes, and the position of an element is its index, starting at 0. A list allows duplicates: the same value can appear several times. The Java documentation says lists "typically" allow duplicates, and the standard implementations all do.

Declare by interface, create by class (Lesson 1):

java

List<String> names = new ArrayList<>();

The core methods

Method	What it does	Returns
`add(x)`	Appends `x` at the end	`true`
`add(i, x)`	Inserts `x` at index `i`, shifting later elements right	nothing
`get(i)`	Reads the element at index `i`	the element
`set(i, x)`	Replaces the element at `i`	the old element
`remove(i)`	Removes the element at index `i`	the removed element
`remove(x)`	Removes the first element equal to `x`	`true` if found
`size()`	Number of elements	`int`
`isEmpty()`	Is `size()` zero?	`boolean`
`contains(x)`	Is some element equal to `x`?	`boolean`
`indexOf(x)`	Index of the first element equal to `x`	index, or `-1` if absent

"Equal" here means equals (BEG-026). That is why contains and remove(x) work for strings by content, and why your own classes need a correct equals before they behave well in a list.

The last valid index is size() - 1. Asking for an index outside 0 to size() - 1 throws an IndexOutOfBoundsException, for example Index 5 out of bounds for length 2.

The `remove` trap on a `List<Integer>`

List has two methods called remove, and Java picks between them by the type of the argument:

remove(int index) removes by position.
remove(Object o) removes by value.

With a list of strings there is no confusion: a String is an object. With a List<Integer>, a plain int argument selects the index version.

java

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 1));
nums.remove(1);                    // index 1: removes 20 -> [10, 30, 1]
nums.remove(Integer.valueOf(1));   // value 1: removes the 1 -> [10, 30]

If you mean "remove the value 1", wrap it as Integer.valueOf(1) (or cast: (Integer) 1). This is a classic source of silent bugs, because the wrong call compiles and runs.

Two implementations: `ArrayList` and `LinkedList`

Both implement List, so the code above works with either. They differ inside.

ArrayList keeps its elements in an array. When the array is full it allocates a bigger one and copies. Consequences:

get(i) and set(i, x) are fast: jump straight to a slot. The documentation states these run in constant time.
Adding at the end is cheap on average ("amortized constant time" in the documentation).
Inserting or removing in the middle or at the front is slower: later elements must shift over, so the cost grows with the list size.

LinkedList is a chain of small node objects, each pointing to the next and previous. Consequences:

Adding or removing at the ends is cheap: just relink nodes.
get(i) is slow: to reach index i it must walk the chain from the nearer end. The documentation says indexed operations traverse the list "from the beginning or the end, whichever is closer".
Each element carries extra node overhead, so it uses more memory per element.

A comparison:

Operation	`ArrayList`	`LinkedList`
`get(i)`	Fast	Slow (walks the chain)
Add at end	Fast on average	Fast
Add or remove at the front	Slower (shifts everything)	Fast
Add or remove in the middle	Slower (shifts)	Fast once you are at that spot, but finding the spot is slow
Memory per element	Low	Higher

The honest rule is: use ArrayList unless you have a measured reason not to. Real programs read by index and iterate far more than they insert at the front. If you need a structure mainly for the ends, a Deque such as ArrayDeque (Lesson 5) is usually a better fit than a LinkedList. The ArrayDeque documentation says it is likely to be faster than LinkedList when used as a queue, so LinkedList is rarely the first choice.

`contains` scans the whole list

contains(x) and indexOf(x) start at index 0 and compare each element with equals until they find a match. If the value is at the end or absent, they look at every element. On 10 elements that is nothing; on a million elements, called thousands of times, it is a real slowdown. This is the "O(n)" idea from BEG-017-L06: the work grows in step with the list size.

If your code mostly asks "is this in there?", a Set (Lesson 3) or a Map (Lesson 4) answers far faster. Lesson 9 measures the difference.

Lists you cannot change

List.of("a", "b") creates a small unmodifiable list. Calling add, remove, or set on it throws UnsupportedOperationException. It also rejects null elements. This is useful for fixed data, but surprising if you forget it. To get a changeable copy, wrap it: new ArrayList<>(List.of("a", "b")).

Examples

Example 1: add, get, remove (simple)

java

List<String> names = new ArrayList<>();
names.add("Ana"); names.add("Omar"); names.add("Ana");
names.add(1, "Lina");
System.out.println(names + " size=" + names.size());
System.out.println(names.get(1) + " " + names.indexOf("Ana") + " " + names.contains("Omar"));
names.set(0, "Zed");
names.remove("Ana");
names.remove(0);
System.out.println(names + " empty=" + names.isEmpty());
try { names.get(5); }
catch (IndexOutOfBoundsException e) { System.out.println(e.getMessage()); }

Output:

text

[Ana, Lina, Omar, Ana] size=4
Lina 0 true
[Lina, Omar] empty=false
Index 5 out of bounds for length 2

Trace it: after add(1, "Lina") the list is [Ana, Lina, Omar, Ana]. set(0, "Zed") gives [Zed, Lina, Omar, Ana]. remove("Ana") removes the first Ana, which is the last element now, giving [Zed, Lina, Omar]. remove(0) removes Zed.

Example 2: the number trap and the unmodifiable list (practical)

java

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 1));
nums.remove(1);
System.out.println(nums);
nums.remove(Integer.valueOf(1));
System.out.println(nums);

List<String> fixed = List.of("a", "b");
try { fixed.add("c"); }
catch (UnsupportedOperationException e) { System.out.println("UOE " + e.getMessage()); }
List<String> copy = new ArrayList<>(fixed);
copy.add("c");
System.out.println(copy);

Output:

text

[10, 30, 1]
[10, 30]
UOE null
[a, b, c]

The first remove(1) took out the element at index 1 (the value 20), not the value 1. The UOE null line shows that the exception exists but carries no message.

Example 3: a to-do list, plus a `LinkedList` swap (realistic)

java

List<String> todo = new ArrayList<>();
todo.add("write"); todo.add("test"); todo.add("ship");
for (int i = 0; i < todo.size(); i++) {
    System.out.println((i + 1) + ". " + todo.get(i));
}
for (String t : todo) System.out.print(t.toUpperCase() + " ");
System.out.println();

List<String> linked = new LinkedList<>(todo);
linked.add(0, "plan");
System.out.println(linked);

Output:

text

1. write
2. test
3. ship
WRITE TEST SHIP 
[plan, write, test, ship]

Two loops read the list: an index loop when you need the position, and a for-each when you do not. The LinkedList copy was created from the same list, and every method we used is a List method, so nothing else changed. That is the payoff of declaring by interface. (A LinkedList can be put in a List variable and, if you declare it as LinkedList, also offers addFirst and getFirst.)

Backend Insight

Most "give me many of X" results in backend code are lists: the orders for a customer, the rows from a query, the items in a JSON array. Frameworks such as Spring and JPA return List<...> from repository methods, and you will read and filter them with the loops you already know. They are nearly always ArrayLists underneath.

The performance habit to build now: a list is great for "walk through everything" and "give me the n-th", and poor for "find this one by value" on big data. A service that keeps 100,000 customers in a List and calls contains or loops to find one by id on every request does 100,000 comparisons per request in the worst case. The fix is a Map keyed by id (Lesson 4), and you will see it measured in Lesson 9.

Common Mistakes

Mistake 1: `remove(1)` on a `List<Integer>`

Incorrect: nums.remove(1) when you meant "remove the value 1".
Correct: nums.remove(Integer.valueOf(1)).

Mistake 2: Off-by-one on indexes

Incorrect: list.get(list.size()) (one past the end).
Correct: list.get(list.size() - 1) for the last element. This is the same off-by-one you studied in BEG-013-L06.

Mistake 3: Choosing `LinkedList` "because inserts are fast"

The insert is only fast after you are positioned at the right node, and getting there is a walk. For most programs ArrayList is faster overall and uses less memory. Pick LinkedList only when you have measured a problem.

Mistake 4: Trying to modify `List.of(...)`

Incorrect: List<String> l = List.of("a"); l.add("b"); throws UnsupportedOperationException.
Correct: List<String> l = new ArrayList<>(List.of("a")); l.add("b");.

Mistake 5: Using `contains` as a fast lookup on large lists

It is a scan. If the list is large and you search often, change the structure, not the loop.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. What does this print?

java

List<String> x = new ArrayList<>(List.of("p", "q"));
x.add(1, "r");
x.set(2, "s");
System.out.println(x + " " + x.get(x.size() - 1) + " " + x.indexOf("z"));

Show solution A1

A1. [p, r, s] s -1. After add(1, "r") the list is [p, r, q]; set(2, "s") replaces q, giving [p, r, s]. The last element is s. indexOf("z") is -1 because it is absent.

A2. A list has 4 elements. Which indexes are valid? What happens with get(4)?

Show solution A2

A2. Indexes 0, 1, 2, 3. get(4) throws IndexOutOfBoundsException (Index 4 out of bounds for length 4).

A3. State the default list implementation and one reason for it.

Show solution A3

A3. ArrayList. It reads by index quickly, adds at the end cheaply, and uses less memory per element than a LinkedList.

Level B: Application

B1. Predict the output, then say what changed if the last line were n.remove(7) instead:

java

List<Integer> n = new ArrayList<>(List.of(5, 6, 7, 8, 7));
n.remove(0);
n.remove(Integer.valueOf(7));
System.out.println(n);

Show solution B1

B1. [6, 8, 7]. remove(0) drops index 0 (the 5), giving [6, 7, 8, 7]; removing the value 7 removes only its first occurrence, giving [6, 8, 7]. With n.remove(7) the int argument picks the index version: index 7 does not exist in a list of four elements, so it throws IndexOutOfBoundsException.

B2. Write static int maxOf(List<Integer> xs) that returns the largest element using an index loop. Assume the list is not empty.

Show solution B2

B2.

java

static int maxOf(List<Integer> xs) {
    int best = xs.get(0);
    for (int i = 1; i < xs.size(); i++) {
        if (xs.get(i) > best) best = xs.get(i);
    }
    return best;
}

For [6, 8, 7] it returns 8.

B3. A teammate wrote List<String> days = List.of("Mon", "Tue"); days.add("Wed"); and got an exception. Name it and fix the code.

Show solution B3

B3. UnsupportedOperationException, because List.of is unmodifiable. Fix: List<String> days = new ArrayList<>(List.of("Mon", "Tue")); days.add("Wed");.

Level C: Challenge

C1. Write static List<String> without(List<String> in, String x) that returns a new list containing every element of in except those equal to x, leaving in unchanged. Test it with [a, b, a, c] and "a".

Show solution C1

C1.

java

static List<String> without(List<String> in, String x) {
    List<String> out = new ArrayList<>();
    for (String s : in) {
        if (!s.equals(x)) out.add(s);
    }
    return out;
}

without(List.of("a", "b", "a", "c"), "a") returns [b, c] and the input still has four elements. We build a new list instead of removing from the one we loop over, which Lesson 7 explains.

C2. A program reads 1,000,000 values by index in a loop. Another inserts 1,000,000 values at the front, one by one. For each, say whether ArrayList or LinkedList is likely to suit better, and explain in two sentences. Then say what you would do before trusting that answer.

Show solution C2

C2. Reading by index suits ArrayList, because get(i) is direct; on a LinkedList each call walks the chain. Inserting at the front suits LinkedList in principle, because it only relinks nodes, while an ArrayList shifts every element on each insert. Before trusting either answer, measure with realistic data and sizes (Lesson 9 shows how), and consider whether a Deque is the better tool for front insertion (Lesson 5).

Mini Challenge

Build a small playlist manager with a List<String>:

Add five song titles, including one duplicate.
Print the playlist numbered from 1.
Remove the first occurrence of the duplicate by value, then remove the last song by index (use size() - 1).
Replace the second song with a new title using set.
Print contains for a title that is there and one that is not, and the indexOf of the second.

Check your work: no IndexOutOfBoundsException, the final list has three songs, and the printed numbers start at 1 while the indexes start at 0.

Summary & Next Lesson

Key takeaways

A List is ordered, indexed from 0, and allows duplicates.
Core methods: add, get, set, remove, size, contains, indexOf, isEmpty. remove has an index version and a value version, which matters for List<Integer>.
ArrayList is backed by an array and is the default. LinkedList is a chain of nodes: fast at the ends, slow get(i).
contains scans the list, so heavy lookup use calls for a Set or Map.
List.of is unmodifiable; copy it into an ArrayList when you need to change it.

Next lesson

The next lesson, "Sets", covers collections where duplicates simply cannot exist, and where "is it in there?" is fast.

Self-check

What is the index of the first element of a list?
What does list.remove(2) do on a List<Integer>: remove the value 2, or the element at index 2?
Why is get(i) slow on a LinkedList?
What does indexOf return when the element is absent?
Which exception does List.of("a").add("b") throw?

Show answers

Index 0.
It removes the element at index 2, because an int argument selects remove(int index). Use Integer.valueOf(2) to remove the value.
It has to walk the chain of nodes from the nearer end to reach the index, instead of jumping straight to a slot.
-1.
UnsupportedOperationException.

References

Oracle, Java SE 21 API, List. Supports ordered lists that typically allow duplicates, the two remove overloads, and that List.of lists are unmodifiable and reject nulls.
Oracle, Java SE 21 API, ArrayList. Supports constant-time get/set/size, amortized constant-time add, and the resizable-array description.
Oracle, Java SE 21 API, LinkedList. Supports that it is a doubly-linked list and that index operations traverse from the nearer end.
Oracle, Java SE 21 API, Collection. Supports that contains is defined in terms of equals.
Oracle, Java SE 21 API, ArrayDeque. Supports that it is likely to be faster than LinkedList when used as a queue.
Program output was produced by compiling and running the examples and solutions with JDK 21. The statement that contains is a linear scan on ArrayList is standard behavior that I did not find stated in the fetched pages; the lesson presents it as general knowledge, to be measured in Lesson 9.

Practice

Apply this lesson with the module's lab, exercises and quiz.

Lab and exercises Quiz

Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.

Continue to next lesson

Lesson Overview

Learning Objectives

Written Explanation

What a list promises

The core methods

The remove trap on a List<Integer>

Two implementations: ArrayList and LinkedList

contains scans the whole list

Lists you cannot change

Examples

Example 1: add, get, remove (simple)

Example 2: the number trap and the unmodifiable list (practical)

Example 3: a to-do list, plus a LinkedList swap (realistic)

Backend Insight

Common Mistakes

Mistake 1: remove(1) on a List<Integer>

Mistake 2: Off-by-one on indexes

Mistake 3: Choosing LinkedList "because inserts are fast"

Mistake 4: Trying to modify List.of(...)

Mistake 5: Using contains as a fast lookup on large lists

Exercises

Level A: Foundation

Level B: Application

Level C: Challenge

Mini Challenge

Summary & Next Lesson

Key takeaways

Next lesson

Self-check

References

Practice

The `remove` trap on a `List<Integer>`

Two implementations: `ArrayList` and `LinkedList`

`contains` scans the whole list

Example 3: a to-do list, plus a `LinkedList` swap (realistic)

Mistake 1: `remove(1)` on a `List<Integer>`

Mistake 3: Choosing `LinkedList` "because inserts are fast"

Mistake 4: Trying to modify `List.of(...)`

Mistake 5: Using `contains` as a fast lookup on large lists