LinkedList and ArrayDeque

the picture

you know how textbooks say "linked lists have O(1) insertion" and then everyone's LinkedList code is slow? both are true, and the gap between them is the whole chapter.

a linked list is a scavenger hunt. each clue (node) tells you where the next one is hidden. getting to clue 500 means reading 499 clues first. a circular buffer is a round table with numbered seats: people join at either end of the queue, and when you run off seat 7 you just keep going at seat 0.

every element costs a whole Node object: a 12-byte header plus item, next and prev (4 bytes each with compressed references) = 24 bytes, on top of the element itself. an array slot is 4 bytes. and those nodes can end up anywhere in the heap, so walking the list means chasing pointers the CPU can't predict.

the get(i) trap

LinkedList implements List, so get(i) compiles and looks innocent. it's a walk. this loop is the classic:

for (int i = 0; i < list.size(); i++) {
    total += list.get(i);   // walks from an end every time
}

on an ArrayList that's n array reads. on a LinkedList each get(i) walks up to n/2 nodes, so the loop is O(n²).

so if you have a LinkedList, never index into it. iterate it (for-each, iterator(), forEach). which raises the question of why you have a LinkedList.

ArrayDeque: the circular buffer

ArrayDeque keeps one array and two indexes: head (the first element) and tail (the next free slot at the back). addLast writes at tail and moves it right. addFirst moves head left and writes there. when either one falls off an end of the array, it wraps to the other end. nothing ever shifts.

the details, from jdk 25's ArrayDeque.java:

• new ArrayDeque<>() makes a 17-slot array (16 + 1). new ArrayDeque<>(7) makes 8. one slot is always kept free, so head == tail can only mean "empty"... except for the instant after an add fills the last slot, which triggers an immediate grow.
• growth: small deques (under 64 slots) grow by capacity + 2, roughly doubling. bigger ones grow by 50%.
• after growing, if the contents wrapped around, the leg from head to the old end is copied to the end of the new array, so the elements are contiguous (in ring order) again.

it's also the right way to do a stack and a queue in java:

void main() {
    Deque<String> stack = new ArrayDeque<>();
    stack.push("a");
    stack.push("b");
    stack.push("c");
    IO.println(stack.pop() + " " + stack.peek());
 
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    IO.println(queue.poll() + " " + queue.peek());
}

c b
a b

push/pop/peek work at the front (stack, LIFO). offer/poll/peek add at the back and take from the front (queue, FIFO). same class, same array.

the numbers

rough numbers from my machine, to make the shapes concrete. this is not a proper benchmark (no JMH): System.nanoTime around whole loops, warmup rounds first, median of 7, and the numbers below agreed within about 10% across three separate runs. jdk 25.0.4 (temurin), apple M4 Pro, default G1 and heap, 100,000 Integers.

the honest surprise: LinkedList isn't that bad at its own game. addLast was about the same speed for all three (allocation is very cheap in the JVM), and for-each iteration was only ~1.6x slower than ArrayList (2.0 vs 1.3 ns per element). that's partly because a freshly built list's nodes were allocated one after another, so they happen to sit next to each other in memory. in a long-running program, after other allocations and a few GCs, they scatter, and the gap grows.

so when do you use LinkedList?

almost never. the one thing it does that ArrayList and ArrayDeque can't: insert or remove in the middle in O(1), if you're already standing there with a ListIterator. no shifting, just relinking. that's real, but rare, and even then a plain ArrayList often wins for small-to-medium lists because shifting a few thousand contiguous references is fast.

Joshua Bloch, who wrote LinkedList, has said publicly that he doesn't use it. take the hint.