SSerguey Asael Shinder
Java coding notes: the JVM, and writing software that lasts

Serguey Asael Shinder: ArrayList.removeLast is constant time, removeFirst is not, and the javadoc says so

· by Serguey Asael Shinder / Serguey Shinder

This week GitHub published a batch of advisories for NLTK, the Python language toolkit. Two of them have the same root cause: a loop that removes the first element of a list with list.pop(0), once per item. Each call shifts every remaining element, so the loop costs time proportional to the square of the input, and a crafted input can keep a worker busy for tens of seconds (GHSA-r53h-rw34-8h97, GHSA-ffr9-mgrr-wcvr).

Java has the same trap, and its documentation spells it out.

The ArrayList javadoc for Java SE 25 gives an explicit list: "The size, isEmpty, get, set, getFirst, getLast, removeLast, iterator, listIterator, and reversed operations run in constant time. The add, and addLast operations runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking)."

removeLast is on the constant-time list. removeFirst is not, and neither is remove(int index), whose own description says it "Shifts any subsequent elements to the left (subtracts one from their indices)". So this loop does the same thing as the NLTK code:

List<Token> work = new ArrayList<>(tokens);
while (!work.isEmpty()) {
    Token t = work.removeFirst();   // or work.remove(0): linear per call
    process(t);
}
Serguey Asael Shinder: ArrayList.removeLast is constant time, removeFirst is not, and the javadoc says so
ArrayList.removeLast is constant time, removeFirst is not, and the javadoc says so — Serguey Asael Shinder

Each removal is linear in what is left, and draining the whole list that way is quadratic in its length.

The class that is documented for this pattern is ArrayDeque. Its javadoc says: "Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time." It adds that the class "is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."

Deque<Token> work = new ArrayDeque<>(tokens);
while (!work.isEmpty()) {
    Token t = work.pollFirst();
    process(t);
}

Two details from the same page matter when switching. ArrayDeque prohibits null elements, so a list that can contain null cannot be moved over unchanged. And it is not thread-safe without external synchronisation, the same as ArrayList.

There is no JDK on the machine I write these notes on, so I have not timed either loop; the claim here is only what the two contracts promise. That is the point, though. The constant-time list in the ArrayList javadoc is short and explicit, and anything not on it, including taking from the front, is documented as linear. When the input size is controlled by someone else, that sentence is the one to check before writing the loop.