Java LinkedList

›Short versionOpen if you only have a minute.

LinkedList is a doubly linked list. Each element is a node with previous and next links.
get, set, and indexed add or remove walk from the nearer end. That walk is linear.
Splicing is cheap only when a list iterator is already on the node.
Ends are cheap: addFirst, addLast, removeFirst, and removeLast are constant time.
For a deque, prefer ArrayDeque. For a list you read by index, prefer ArrayList.
Extra node objects and scattered memory make a full scan slower than the same scan on an ArrayList.

A stores each element in a . Rewiring a node you already hold really is a handful of assignments. The mistake is treating that picture as the cost of add(i, e) or get(i).

Those calls start with an . For ordinary list code — read by position, append, search with equals — that walk makes LinkedList the wrong default. ArrayList does the read in constant time and keeps elements adjacent in memory.

When the links are actually cheap

Hold a and the cursor is the node. add and remove on that iterator splice without searching again. A long walk that inserts or deletes at the cursor, and only at the cursor, is the textbook case.

The other cheap case is the ends. LinkedList is a . If you only need a stack or a queue, ArrayDeque does those end operations without a node object per element. The LinkedList javadoc points you there for queue use.

finishes the comparison. Even a full scan, which is linear either way, usually favors the array because each step moves to the next slot instead of chasing a pointer.

Operations:

ℹ️ Ready to modify the LinkedList!

Head

Node 0

HEAD

Node A

Node 1

Tail

Node 2

TAIL

Ends, and a cursor that already arrived

LinkedListDemo.java

LinkedList<String> names = new LinkedList<>();
names.addFirst("Ada");
names.addLast("Grace");     // constant time at the ends
names.get(1);               // walks, even though 1 is near

ListIterator<String> cursor = names.listIterator();
cursor.next();
cursor.add("Lin");          // splice beside the cursor, no second search

Deque<String> queue = new ArrayDeque<>();
queue.addLast("Ada");       // the usual deque

A loop calls list.get(i) for i from 0 to size() - 1 on a LinkedList. What is the total cost, and what should the loop do instead?

Each get walks about min(i, n − i) nodes, so the loop is quadratic. Use an iterator or a for-each loop, which hop once per element and finish in linear time. If the body only needed the index, an ArrayList would make each get constant time.