List and Deque · Layers of Logic

This page is for looking things up. Section 10.4 is where these classes are explained and where the measurements are.

Everything on this page was compiled and run on Java 21 before it was written down. Where a method throws, the exception named is the one it actually threw.

Start here if you’re choosing

	What your program does	Use this
Anything, and you are not sure yet	the default	ArrayList
Read and write by position	get(i) and set(i, e) are hot	ArrayList
Add and remove at both ends	a queue or a stack	ArrayDeque
A stack, last in first out	push and pop only	ArrayDeque, never Stack
You need null in the collection	ArrayDeque refuses null	LinkedList or ArrayList
Old code you cannot change	you will meet these	Vector and Stack, read only

Every List has these

List is the interface. ArrayList, LinkedList, Vector and Stack all implement it, so every method here works on all four.

Reading

Method	What it does	When it's empty or absent	Watch out
`get(int i)`	The element at position i.	Throws `IndexOutOfBoundsException`.	Instant on `ArrayList`. On `LinkedList` it walks from the nearer end.
`size()`	How many elements are in it.	Returns `0`.
`isEmpty()`	True when size is 0.	Returns `true`.	Say this rather than `size() == 0`. It reads better and it is what people look for.
`contains(Object o)`	True if the element is in the list.	Returns `false`.	Walks the whole list. On a big list in a loop, this is where the time goes. A `Set` answers the same question without walking.
`indexOf(Object o)`	Position of the first match.	Returns `-1`, it does not throw.	Verified: `List.of(1,2).indexOf(9)` is `-1`.
`lastIndexOf(Object o)`	Position of the last match.	Returns `-1`.

Changing

Method	What it does	When it's empty or absent	Watch out
`add(E e)`	Adds to the end. Returns true.		Always returns `true` for a list, because a list never refuses a duplicate. On a `Set` the same method means something.
`add(int i, E e)`	Inserts at position i and shifts the rest right.	Throws `IndexOutOfBoundsException` unless i is 0.	This is the one people confuse with `set`. add grows the list by one.
`set(int i, E e)`	Replaces what is at position i. Returns the old value.	Throws `IndexOutOfBoundsException`.	set does not change the size.
`remove(int i)`	Removes by <strong>position</strong>. Returns what was removed.	Throws `IndexOutOfBoundsException`.	On a `List<Integer>`, `remove(1)` removes position 1, not the value 1. This is the most famous trap in the framework.
`remove(Object o)`	Removes the first match by <strong>value</strong>. Returns true if it removed anything.	Returns `false` and changes nothing.	To force this one on a list of numbers, write `remove(Integer.valueOf(1))`.
`clear()`	Removes everything.	Does nothing. Safe on an empty list.
`addAll(Collection c)`	Adds all of them to the end.		Returns `true` if the list changed.
`removeIf(Predicate p)`	Removes every element matching the test.		The safe way to remove while looping. Doing it by hand inside a for-each throws `ConcurrentModificationException`.
`replaceAll(UnaryOperator op)`	Runs the function over every element in place.		Changes the list. It does not hand you a new one.
`sort(Comparator c)`	Sorts the list in place.		Pass `null` to use the natural order, or use `Comparator.naturalOrder()`, which says what you mean.

Views and copies

Method	What it does	When it's empty or absent	Watch out
`subList(int from, int to)`	A window onto part of the same list.	Throws `IndexOutOfBoundsException` if the range is bad.	It is a view, not a copy. Change the view and you change the original. For a copy write `new ArrayList<>(list.subList(a, b))`.
`iterator()`	A cursor over the elements, front to back.		Its `remove()` is the only safe way to delete during a manual walk.
`toArray()`	A new array holding the elements.	Returns an empty array.	Use `toArray(new String[0])` to get a typed array back rather than `Object[]`.

What Java 21 added to every List

Java 21 introduced SequencedCollection, and List extends it. So these four now work on a plain ArrayList, with no LinkedList and no Deque involved.

Most tutorials you’ll find online were written before this and don’t mention it.

Ends of any List, Java 21 and later

Method	What it does	When it's empty or absent	Watch out
`getFirst()`	The first element.	Throws `NoSuchElementException`.	Verified on Java 21: `List.of(1,2,3).getFirst()` is `1`.
`getLast()`	The last element.	Throws `NoSuchElementException`.	Replaces `list.get(list.size() - 1)`, which was easy to get wrong on an empty list.
`addFirst(E e)`	Puts it at the front.		On an `ArrayList` this shifts everything right, so it is still slow. The method being available does not make it cheap.
`addLast(E e)`	Puts it at the end.		The same as `add(e)`.
`removeFirst()`	Removes and returns the first element.	Throws `NoSuchElementException`.
`removeLast()`	Removes and returns the last element.	Throws `NoSuchElementException`.
`reversed()`	A reversed view of the list.		Verified: `List.of(1,2,3).reversed()` is `[3, 2, 1]`. It is a view, so it costs nothing to make.

Deque: both ends, three ways each

ArrayDeque and LinkedList both implement Deque. Every operation at an end comes in three versions, and the only difference between them is what happens when the deque is empty.

This is the table to remember, because picking the wrong column is how you get a crash at three in the morning.

	If it fails	You get
The throwing version	getFirst, removeFirst, element, pop	NoSuchElementException
The null version	peekFirst, pollFirst, peek, poll	null, quietly
The boolean version	offerFirst, offerLast, offer	false, when the deque is full

At the front

Method	What it does	When it's empty or absent	Watch out
`addFirst(E e)`	Adds at the front.	Throws `IllegalStateException` if the deque is full.
`offerFirst(E e)`	Adds at the front. Returns whether it worked.	Returns `false` instead of throwing.
`getFirst()`	Reads the front without removing it.	Throws `NoSuchElementException`.
`peekFirst()`	Reads the front without removing it.	Returns `null`.	Verified. This is the pair to be careful with: `getFirst` throws where `peekFirst` hands you a `null` that travels somewhere else before it fails.
`removeFirst()`	Removes and returns the front.	Throws `NoSuchElementException`.
`pollFirst()`	Removes and returns the front.	Returns `null`.

At the back

Method	What it does	When it's empty or absent
`addLast(E e)`	Adds at the back.	Throws `IllegalStateException` if the deque is full.
`offerLast(E e)`	Adds at the back. Returns whether it worked.	Returns `false`.
`getLast()`	Reads the back without removing it.	Throws `NoSuchElementException`.
`peekLast()`	Reads the back without removing it.	Returns `null`.
`removeLast()`	Removes and returns the back.	Throws `NoSuchElementException`.
`pollLast()`	Removes and returns the back.	Returns `null`.

Using a Deque as a queue

Method	What it does	When it's empty or absent	Watch out
`offer(E e)`	Adds at the back. Same as offerLast.	Returns `false` when full.
`poll()`	Removes from the front. Same as pollFirst.	Returns `null`.	This is the pair to use for a work queue, because an empty queue is normal rather than exceptional.
`peek()`	Reads the front. Same as peekFirst.	Returns `null`.
`element()`	Reads the front. Same as getFirst.	Throws `NoSuchElementException`.

Using a Deque as a stack

Method	What it does	When it's empty or absent	Watch out
`push(E e)`	Puts it on top. Same as addFirst.		The top of an `ArrayDeque` stack is the front.
`pop()`	Removes and returns the top. Same as removeFirst.	Throws `NoSuchElementException`.	Note that `Stack.pop()` throws `EmptyStackException` instead. Different class, different exception.
`peek()`	Reads the top without removing it.	Returns `null`.	`Stack.peek()` throws instead of returning null. Another difference between the two.
`descendingIterator()`	Walks from the back to the front.		Verified on `[1, 2, 3]`: it yields 3, then 2, then 1.

Three things that catch people out

ArrayDeque refuses null. Verified: deque.add(null) throws NullPointerException. LinkedList and ArrayList both accept null happily. The reason is that poll() and peek() use null to mean “nothing there”, so a stored null would be impossible to tell apart from an empty deque.

Stack and ArrayDeque print in opposite orders. This one surprises everybody. Push 1 then 2 into each, then print:

Stack<Integer> s = new Stack<>();
s.push(1); s.push(2);
System.out.println(s);        // [1, 2]   bottom first

ArrayDeque<Integer> d = new ArrayDeque<>();
d.push(1); d.push(2);
System.out.println(d);        // [2, 1]   top first

Both are correct and they disagree, because Stack prints as the Vector it inherits from, while ArrayDeque prints from its front, and its front is the top of the stack. If you’re checking a stack by printing it, know which one you’re holding.

Arrays.asList gives you a fixed-size list. Verified: set works on it, and add throws UnsupportedOperationException. It’s a view over the array you passed in, so it can change values but not the length. List.of is different again, and refuses both. List.copyOf also throws NullPointerException if the source holds a null.

What each class costs

	Class	Cost and character
ArrayList	one array, resized	get(i) instant. Some spare capacity wasted on purpose. The default
LinkedList	one Node object per element	roughly six times the memory. Fast at the ends, slow by position
ArrayDeque	one circular array	faster than LinkedList at both ends. No get(i). Refuses null
Vector	ArrayList with every method locked	slower, and not as thread safe as it looks. Do not use
Stack	extends Vector	inherits get(i) and add(i, e), which defeat the point. Do not use