The Collections Framework

LinkedList & the List Interface

15 min Lesson 3 of 14

LinkedList & the List Interface

You already know that ArrayList stores elements in a contiguous array. LinkedList takes the opposite approach: every element lives in its own node that holds a reference to the next and previous nodes. Understanding this internal difference is the whole story of when to choose one over the other.

The List Interface — the contract both share

Both ArrayList and LinkedList implement java.util.List<E>. That interface defines the operations every ordered, index-based collection must support:

add(E e) / add(int index, E e) — append or insert
get(int index) — retrieve by position
set(int index, E e) — replace by position
remove(int index) / remove(Object o) — delete by index or value
size(), contains(Object o), indexOf(Object o)
subList(int from, int to), sort(Comparator<? super E> c)

Programming to the List interface rather than a concrete class is a core Java idiom. It lets you swap the implementation later without touching the rest of your code:

// declare as List — not ArrayList or LinkedList
List<String> names = new ArrayList<>();
// swap to LinkedList any time — nothing else changes
// List<String> names = new LinkedList<>();

names.add("Alice");
names.add("Bob");
names.add(1, "Charlie"); // insert at index 1
System.out.println(names); // [Alice, Charlie, Bob]
System.out.println(names.get(0)); // Alice

Declare variables as List, not ArrayList. Method signatures that accept List<String> work with any implementation. Signatures that demand ArrayList<String> lock you in — that is usually a mistake.

How LinkedList works internally

LinkedList is a doubly linked list. Each node looks roughly like this:

// conceptual — not the actual JDK source
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

The list object keeps references to the first and last nodes only. To reach node number k, Java must walk the chain from one end — O(n) time. Inserting or deleting at a known node, however, is O(1): just rewire three pointers.

import java.util.LinkedList;
import java.util.List;

LinkedList<Integer> scores = new LinkedList<>();
scores.add(10);
scores.add(20);
scores.add(30);

// insert at the front — O(1)
scores.addFirst(5);
// insert at the back — O(1)
scores.addLast(35);

System.out.println(scores); // [5, 10, 20, 30, 35]

// remove from the front — O(1)
int head = scores.removeFirst();
System.out.println(head); // 5
System.out.println(scores); // [10, 20, 30, 35]

LinkedList also implements Deque<E>, which is why it exposes addFirst, addLast, peekFirst, pollLast, and so on — methods that ArrayList does not have.

ArrayList vs LinkedList — the trade-off table

These are the Big-O complexities that drive the decision:

Random access (get(i)): ArrayList O(1) vs LinkedList O(n). ArrayList wins decisively — it jumps straight to the backing array index.
Append at the end (add(e)): Both are O(1) amortised. ArrayList occasionally resizes; LinkedList always allocates a new node.
Insert/delete in the middle (add(i, e) / remove(i)): ArrayList O(n) because elements must shift; LinkedList O(n) to find the index, then O(1) to rewire. Neither wins clearly unless you already hold an iterator at the insertion point.
Insert/delete at the front: ArrayList O(n) (every element shifts right); LinkedList O(1). This is the one case LinkedList clearly outperforms ArrayList.
Memory: ArrayList is more compact (one array). Each LinkedList node allocates two extra object references, making the per-element overhead 3–4× higher.

In practice, ArrayList wins almost every benchmark. Modern CPUs are dramatically faster at iterating a contiguous array (cache-line locality) than chasing pointers across heap memory. Prefer ArrayList by default; reach for LinkedList only when you specifically need O(1) front insertions/deletions or the Deque interface.

Iterating a LinkedList efficiently

Never use index-based loops on a LinkedList. Each get(i) call walks the chain from the head, turning an O(n) iteration into O(n²).

LinkedList<String> items = new LinkedList<>(List.of("a", "b", "c", "d"));

// WRONG — O(n²) because each get(i) walks from the head
for (int i = 0; i < items.size(); i++) {
    System.out.println(items.get(i));
}

// CORRECT — enhanced for-loop uses the iterator internally — O(n)
for (String item : items) {
    System.out.println(item);
}

// Also correct — explicit iterator
var it = items.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Never call get(index) in a loop on a LinkedList. This is one of the most common performance mistakes Java developers make. Always iterate with the enhanced for-loop or an explicit Iterator / ListIterator.

Using LinkedList as a Deque

When you need a queue (FIFO) or a stack (LIFO) backed by a linked structure, LinkedList is a ready-made option:

import java.util.Deque;
import java.util.LinkedList;

// use as a queue: add to tail, remove from head
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
queue.offer("third");
System.out.println(queue.poll()); // first

// use as a stack: push and pop from head
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Summary

The List interface defines the contract; ArrayList and LinkedList are two implementations with very different internal structures. Prefer ArrayList for general-purpose lists — it has better cache performance and is faster for random access. Use LinkedList when you need constant-time insertions at the front, or when you want a Deque without pulling in ArrayDeque. Always declare variables as List (or Deque) so the implementation stays swappable.