LinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Nodes, not contiguous memory
A LinkedList is a chain of node objects. Each node holds an element plus prev and next references to its neighbors. Inserting or removing at either end is O(1) — just rewire two pointers. But random access is O(n) because you must walk the chain, and each step is a pointer chase that defeats CPU caching.
The Deque interface
Deque (double-ended queue) is the interface LinkedList implements alongside List. It exposes addFirst, addLast, peekFirst, pollLast, plus stack aliases (push, pop) and queue aliases (offer, poll). Program to Deque when you need those operations — that documents intent and lets you swap in ArrayDeque later.
Why LinkedList disappoints
In theory LinkedList beats ArrayList for middle-insertion. In practice, ArrayList almost always wins because contiguous memory is fast on modern CPUs. Every LinkedList operation allocates a node object, and traversal thrashes the cache. Benchmarks routinely show ArrayList.add(i, v) outrunning LinkedList.add(i, v) up to lists with thousands of elements.
When it does earn its keep
Frequent inserts and removes while holding an Iterator are O(1) — the iterator already sits on the node. Priority-less work queues that only touch the ends benefit. And when you specifically need Deque behavior on a List API, LinkedList is the only JDK class that gives you both.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
The recommended default
For a queue or stack, use ArrayDeque. For a general-purpose list, use ArrayList. Reach for LinkedList only when a benchmark says so — and always type the variable as Deque or List so you can swap the implementation without touching the rest of the code.