You need to insert a gift card after the current line item, or you reach for new LinkedList<>() because “inserts are O(1).” The first of those can be true. The second is how open-order lists and warehouse queues get a node object per element and a linear get(i).
LinkedList is a doubly linked deque that also implements List. It is not the default list and not the default queue. The series hub owns fail-fast, optional operations, and RandomAccess. Node layout lives on Linked Lists. This post is the JDK class: when the same nodes are List and Deque, why get(i) walks, and why ArrayList and ArrayDeque usually already won.
The lab is still Order and LineItem from the hub. If records are new, Java Records is the shape.
The type people new by folklore
A warehouse pick list is FIFO. This compiles, and it is the most common LinkedList in production code review:
import java.util.LinkedList;
import java.util.Queue;
public final class PickQueue {
private final Queue<Order> picks = new LinkedList<>();
public void enqueue(Order order) {
picks.offer(order);
}
public Order take() {
return picks.poll();
}
}offer / poll are the Queue verbs. LinkedList implements Queue because it implements Deque. Ends are O(1). That part is honest. The part that is not: you paid a Node per order (item, prev, next, object header) and you bought a List you will almost never index. ArrayDeque is the same ends on a circular array, no node objects, and a hard “no nulls” that makes poll() == null mean empty.
Write new ArrayDeque<>() for a queue or stack unless you already needed List on the same object. The rest of this post is that “unless.”
What it actually is
java.util.LinkedList extends AbstractSequentialList and implements List, Deque, and therefore Queue. On Java 21 it is a SequencedCollection through those interfaces — first, last, reversed — see Sequenced Collections. It is fail-fast, unsynchronized, and allows null.
Each element sits in a node:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Java 7+ keeps first and last pointers. An empty list is first == last == null. There is no header sentinel in modern OpenJDK (older textbooks still draw one). addFirst / addLast rewire two or three pointers. get(i) does not; it walks.
| Contract | What LinkedList delivers | Usually prefer |
|---|---|---|
List | Indexes, subList, ListIterator | ArrayList |
Deque / Queue | addFirst, addLast, poll, offer | ArrayDeque |
SequencedCollection | getFirst, getLast, reversed | ArrayList or ArrayDeque |
List + Deque in one object | The rare honest win | LinkedList |
Program to List or Deque on fields. new LinkedList<>() only when the implementation story is nodes.
API and cost: the walk is the bill
Read this as “what you pay,” not as “LinkedList is slow.” Ends are cheap. Indexes are not.
| Method | Cost | Why |
|---|---|---|
addFirst / addLast / offer / offerFirst / offerLast | O(1) | Rewire first / last |
removeFirst / removeLast / poll / pollFirst / pollLast | O(1) | Unlink an end node |
getFirst / getLast / peek | O(1) | Read first or last |
get(i) / set(i, e) | O(n) | Walk from the nearer end |
add(i, e) / remove(i) | O(n) | Walk to i, then splice (O(1) once you are there) |
add(e) (List append) | O(1) | Same as addLast |
remove(Object) / contains | O(n) | Scan nodes |
listIterator then add / remove | O(1) at the cursor | You already hold the node |
size() | O(1) | Cached size field |
subList | view | Same view rules as List |
get(i) starts at first when i < size/2, otherwise at last, and follows next or prev. Mid-list is still Θ(n). A for-loop of get(i) is accidentally quadratic:
static BigDecimal sumIndexed(List<Order> orders) {
BigDecimal total = BigDecimal.ZERO;
for (int i = 0; i < orders.size(); i++) {
total = total.add(orders.get(i).total());
}
return total;
}On an ArrayList each get is O(1). On a LinkedList each get restarts a walk. Iterate with for-each / an iterator if the list is linked. The hub RandomAccess marker is how algorithms tell these apart: ArrayList has it, LinkedList does not. This post will not re-define the marker.
Deque methods and List methods are the same nodes with different names:
LinkedList<Order> picks = new LinkedList<>();
picks.addLast(order); // Deque / List append
picks.add(order); // List: also the tail
picks.offer(order); // Queue: tail, returns boolean
Order next = picks.poll(); // Queue: head or null if empty
Order first = picks.removeFirst(); // Deque: head or NoSuchElementException
Order byIndex = picks.get(2); // List: O(n) walkoffer / poll / peek are the Queue shape (empty → false / null). add / remove / element throw on a failed capacity-restricted deque; LinkedList is unbounded, so add and offer both succeed until memory dies. The useful difference on this class is empty-list behavior: poll() returns null, removeFirst() throws. That collides with “null is a legal element,” which is the next section.
Nulls, memory, and why ArrayDeque already won the ends
LinkedList allows null. ArrayDeque does not — null is how the circular array marks an empty slot. That single internal is a decision:
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.LinkedList;
public final class LineItems {
static LinkedList<LineItem> withGap() {
LinkedList<LineItem> items = new LinkedList<>();
items.add(new LineItem("SKU-1", 1, new BigDecimal("9.99")));
items.add(null);
items.add(new LineItem("SKU-2", 2, new BigDecimal("4.50")));
return items;
}
static void dequeRejectsNull() {
ArrayDeque<LineItem> ends = new ArrayDeque<>();
ends.addLast(new LineItem("SKU-1", 1, new BigDecimal("9.99")));
ends.addLast(null);
}
}withGap() is legal. dequeRejectsNull() throws NullPointerException on the second addLast. If your queue uses poll() == null to mean empty, a LinkedList that also stores null makes empty and “a null order” the same return. That is a reason to forbid nulls in the domain, and a reason ArrayDeque is the safer queue even before locality.
Memory is the other internal. Each LineItem in an ArrayList is one reference in a contiguous Object[] (plus leftover capacity). Each LineItem in a LinkedList is that reference plus a Node: header, item, next, prev. On a 64-bit JVM that is commonly a few dozen extra bytes per element, scattered on the heap. A linear scan of an ArrayList rides cache lines. A linear scan of a LinkedList is a pointer chase. GC sees one extra object per row.
The node tax is why LinkedList loses as a default List and as a default Deque. Ends are O(1) on both LinkedList and ArrayDeque. Only one of those layouts is contiguous.
As a List it loses to ArrayList
The List contract is indexes. ArrayList.get(i) is O(1). LinkedList.get(i) is a walk. Append is O(1) on both (amortized on ArrayList; pointer rewiring here). The folklore is “LinkedList if we insert in the middle.” The accurate version is the data-structures post: splice is O(1) when you already hold the node.
Insert at index 50_000 from the List API:
static void insertAt(List<LineItem> items, int index, LineItem extra) {
items.add(index, extra);
}On LinkedList, add(index, e) walks to index, then relinks. Walk is O(n). On ArrayList, add(index, e) System.arraycopys the tail. Also O(n), but the slide is a tight copy, not a chase plus a new Node. At real sizes the array often wins even for mid-list insert by index.
A for-each is fine on both. An indexed for is the LinkedList footgun. Keep ArrayList for Order.items() unless the next section’s splice is the actual hot path.
subList is still a view. Clearing items.subList(1, 3) unlinks those nodes on the parent. Same warning as ArrayList: do not confuse it with new LinkedList<>(items.subList(1, 3)).
As a Deque it loses to ArrayDeque
Stacks and queues are end-only. ArrayDeque grows a circular array (same amortized story as ArrayList, no index get that you should use). LinkedList as a deque still allocates a node per offer.
import java.util.ArrayDeque;
import java.util.Deque;
public final class RushStack {
private final Deque<Order> rush = new ArrayDeque<>();
public void push(Order order) {
rush.addFirst(order);
}
public Order pop() {
return rush.removeFirst();
}
}That is the default. new LinkedList<>() in the same field compiles and passes a Deque test. It loses on allocation, locality, and the null/poll collision. ArrayDeque is the next post; it does not implement List. If you need get(i) on a queue, you probably needed two structures, or you needed a list and should not have called it a queue.
Vector / Stack are the legacy synchronized answers. They are not a reason to keep LinkedList as a stack. The legacy collections post is where those names go to retire.
The rare win: a held cursor, or List plus Deque
Two honest uses remain.
You already hold a ListIterator (the node) and you splice. ListIterator.add / remove on a LinkedList relink at the cursor. The walk was the iteration you were already doing. The extra insert does not slide the rest of an array:
import java.math.BigDecimal;
import java.util.List;
import java.util.ListIterator;
public final class GiftWrap {
public static void insertCardAfterGift(List<LineItem> items) {
ListIterator<LineItem> it = items.listIterator();
while (it.hasNext()) {
LineItem item = it.next();
if (item.sku().equals("GIFT")) {
it.add(new LineItem("CARD", 1, BigDecimal.ZERO));
}
}
}
}On a LinkedList, each it.add is O(1) pointer work at that node. On an ArrayList, each it.add still copies the tail from the cursor. If you splice many times during one pass, nodes can win. If you splice once on a small list, ArrayList still wins on constants. The linked lists post is the layout version of the same sentence.
You need List and Deque on one object without copying. A structure that is both “index this line item” (rarely) and “push rush orders on the front” (often) can stay a LinkedList. That combination is uncommon. Most services keep an ArrayList of items and an ArrayDeque of work. Two types, two hot operations, no node tax on the list.
Fail-fast still applies. Structural addLast from another iterator during a for-each throws ConcurrentModificationException. ListIterator.add on the iterator you are walking is the supported splice. The hub owns the iterator contract; do not catch CME as control flow.
LinkedList is not thread-safe. Do not share it across workers. A concurrent hand-off is a BlockingQueue, not a linked list you synchronized by folklore.
When not LinkedList
Skip this class when:
- You wanted a default
List. That is ArrayList. Indexes, scans, append,RandomAccess. - You wanted a default queue or stack. That is ArrayDeque. Same
O(1)ends, no nodes, no nulls. - You insert at index
iwithout a cursor. You still walk. Measure againstArrayList.add(i, e)before you celebrateO(1)splice. - The list is small. Twenty line items is not a locality story.
ArrayListis simpler and faster. - You needed uniqueness or a key.
containsis a scan. Set/Map.
The cargo-cult line from the hub is the whole post in one sentence: LinkedList as a default list or deque is a layout you did not need.
Interview lens
Interviewers want to hear that you will not default to LinkedList, and that you know why get(i) is linear anyway.
Complexity they expect: get(i) O(n), addFirst / addLast O(1), add(i, e) O(n) to find the node then O(1) relink, iteration O(n) with an iterator but O(n²) with get(i) in a counted for. Space: O(n) nodes, more bytes per element than ArrayList.
What to draw. first and last, three nodes with prev / next / item. Show addFirst rewiring. Show get(2) walking from first (or from last if the index is in the back half). Cross out a counted for of get(i). Optionally draw an ArrayList Object[] next to it and label “contiguous vs chase.”
Typical questions:
| Question | Honest answer |
|---|---|
Why is get(i) linear? | Nodes are not contiguous. The implementation walks from first or last, whichever is closer. No index arithmetic. |
Why do people still new LinkedList<>() for a queue? | Folklore from “inserts are O(1),” plus Queue being on the type. The JDK default for those ends is ArrayDeque. |
Memory vs ArrayList? | One Node object per element (item, prev, next) vs one slot in an Object[]. Worse locality, more GC. |
| Deque methods vs List methods? | Same nodes. addLast / offer / add all append. get(i) is the List tax the Deque API does not make you pay. |
Nulls vs ArrayDeque? | LinkedList allows null. ArrayDeque forbids it (poll() == null can mean empty). |
| When is insert actually faster? | When you already hold the node / ListIterator and splice. Insert-at-i still walks. |
Does it implement RandomAccess? | No. ArrayList does. Indexed loops should not assume cheap get. |
List + Deque in one type? | That is the rare honest reason to new LinkedList<>(). Most code wants one or the other, not both. |
Wrong answer: “LinkedList is faster at inserts so it is the better default List.” Insert at an index still walks. Append is already cheap on ArrayList. The default List stays ArrayList. Nodes win when you already hold the cursor, or when you truly need List and Deque together.
Cheat sheet
Layout doubly linked nodes; first / last pointers (no sentinel in modern JDK)
Implements List, Deque, Queue, SequencedCollection (Java 21)
get(i)/set(i) O(n) walk from nearer end
addFirst/Last O(1) rewire ends
add(i, e) O(n) walk, then O(1) splice
ListIterator splice at cursor is O(1) — the rare win
nulls yes (ArrayDeque: no)
memory extra Node per element; pointer chase on scans
as List lose to ArrayList
as Deque lose to ArrayDeque
honest use held ListIterator splice, or List+Deque in one object
threads no; fail-fast iterator (hub)
RandomAccess noDo:
new ArrayDeque<>()for a queue or stack.new ArrayList<>()forOrder.items()and any list you index.- Splice through a
ListIteratorwhen the list is already linked and the cursor is the hot path.
Don’t:
- Default to
LinkedListbecause inserts are “O(1)”. for (int i …) list.get(i)on aLinkedList.- Store null in a
LinkedListused as aQueueand then treatpoll() == nullas empty. - Use it as a thread-safe hand-off.
Wrap-up
LinkedList is a doubly linked list of nodes that speaks List and Deque. Ends are O(1). Indexes walk. Each element is an extra object. As a list it loses to ArrayList. As a queue or stack it loses to ArrayDeque. Keep it for a held ListIterator splice, or for the uncommon object that must be both contracts at once.
The default for stacks and queues is the circular array that forbids null and does not implement List. That is the next class.