Linked Lists

An array must shift half its elements to insert in the middle. A linked list just rewires two pointers. It is the structure behind LRU caches, undo histories and the free lists inside memory allocators.

beginner⏱ 8 min read

←Builds on

1Arrays & Dynamic ArraysA linked list trades the array's O(1) indexing for O(1) insertion anywhere.

Leads to→

3Queue (FIFO) & DequeA queue can be a linked list with a head and a tail pointer.5Trees: Concepts, Properties, TraversalsA tree node is a linked list node with several next pointers instead of one.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Nodes joined by pointers

An array is one contiguous block, so the address of a[i] is simple arithmetic: base + i · size. That is why indexing is O(1).

A linked list gives up that block. Each element lives in its own node with two fields: the value and a next pointer to the following node. The nodes can sit anywhere in memory. You only keep a pointer to the first node, the head, and the last node points to null.

The price is access: to reach the 5th element you must start at head and follow next four times. There is no shortcut, so access and search cost O(n).

02Insert and delete by rewiring

Once you hold a pointer to node p, inserting a new node n after it takes two assignments:

n.next = p.next
p.next = n

No element moves, so it is O(1) regardless of the list length. Deleting the node after p is one assignment: p.next = p.next.next. Deleting the head is head = head.next.

The order of the two assignments matters. If you write p.next = n first, the only pointer to the rest of the list is overwritten, and the tail is lost. This is the classic linked list bug. Draw the boxes and arrows on paper before you code it.

The green link is set first, then the blue one; the red link disappears.

03Variants and when to use one

A doubly linked list adds a prev pointer, so you can walk both ways and delete a node in O(1) given only that node. C++ std::list is doubly linked. A circular list links the tail back to the head.

In practice, arrays (vector) win most of the time: they are compact and the CPU cache loves contiguous memory, so even an O(n) shift is often faster than chasing pointers. Reach for a linked list when you keep pointers to nodes and insert or delete around them often, for example an LRU cache (hash map + doubly linked list) or splicing lists together in O(1).

In interviews, linked lists test pointer discipline: reversing, finding the middle, detecting a cycle.

Cost at a glance

Access i-th elementO(n)

SearchO(n)

Insert / delete at a known nodeO(1)

Insert at headO(1)

Remember

A linked list stores each element in a node that points to the next one, so nodes need not be contiguous.
Insertion and deletion at a node you already hold are O(1), but reaching a position or searching is O(n).
When inserting, link the new node to the rest of the list before redirecting the previous node, or the tail is lost.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the insert: the new node gets its next pointer before the old node is redirected. Try searching for a value that is not in the list.

Interactive visualizerfocus here, then space ← →

Singly linked list

A linked list stores each element in its own node that points to the next. Nodes can live anywhere in memory.

Pseudocode

 1 node: { value, next } 2 traverse: follow next pointers  // O(n), no random access 3 insert after p: create node n 4   n.next = p.next; p.next = n   // order matters! 5 delete head: head = head.next   // O(1)

1 / 1

Check

Three questions. Pick an answer to see why.

To insert node n after node p, which order of assignments is correct?

You need fast access to the k-th element for many random k. Which structure?

A list holds 12 → 5 → 8 → 23 and you run head = head.next. What does the list look like now?

Practice

Real problems to lock it in, easiest first.

LeetCodeReverse Linked List beginner↗LeetCodeMerge Two Sorted Lists beginner↗LeetCodeLinked List Cycle beginner↗LeetCodeRemove Nth Node From End of List intermediate↗