Pointer Walk

Linked Lists

Blocks joined by arrows. Reversing a list moves no data at all: three markers walk along and turn each arrow around.

Data StructuresBeginner8 min read

Boxes joined by arrows

An array keeps its items side by side in memory. A linked list does not. Each item sits in its own small box, called a node, and a node holds two things:

  • a value, and
  • an arrow (a pointer) to the next node.

The list itself is just a pointer to the first node, the head. To read the list you start at the head and follow arrows until an arrow points at nothing.

python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(1, Node(2, Node(3)))      # 1 -> 2 -> 3 -> None

What that buys you, and what it costs

Example

Insert in the middle

To put a new node between 2 and 3, point the new node at 3, then point 2 at the new node. Two arrows change. Nothing else in the list is touched.

In an array, everything after that position would have to shift one place to make room.

Good at

  • Insert or remove anywhere by changing one or two arrows
  • Grows one node at a time, with no resizing and no copying

Where it bites

  • No jumping to position 500: you must walk there from the head
  • Each node needs extra memory for its arrow
  • Nodes are scattered in memory, which makes walking them slower than walking an array

Reversing a list without moving anything

This is the classic linked list exercise, and it shows what "the arrows are the structure" really means. To reverse 1 → 2 → 3 → 4 → 5, no node moves and no value is copied. Each arrow is simply turned around.

It takes three markers that walk along the list together:

  • curr: the node whose arrow is about to be turned.
  • prev: the node before it, which is where the arrow will point.
  • nxt: the node after it, saved so the rest of the list is not lost.
Reversing a linked listInteractive
1prev = None
2curr = head
3while curr is not None:
4 nxt = curr.next
5 curr.next = prev
6 prev = curr
7 curr = nxt
8head = prev
1▲head
→
2
→
3
→
4
→
5

Grey arrows still point forwards. Pink arrows have been turned around.

Start. A list of five nodes. Each node holds a value and an arrow to the next node. The goal: make every arrow point the other way.

  1. Save the way forward

    nxt = curr.next. Once curr's arrow is turned, this would be the only way left to reach the rest of the list.

  2. Turn the arrow

    curr.next = prev. The node now points backwards.

  3. Step both markers forward

    prev = curr, then curr = nxt.

  4. Repeat until curr falls off the end

    The last node visited is the new head.

Each node is visited once and only three extra variables are used, however long the list is.

Where you will meet it

  • Queues and stacks in standard libraries are often linked lists underneath.
  • LRU caches keep items in a linked list so that moving one to the front is a few arrow changes. See Cache Eviction Policies.
  • Hash tables that use chaining keep a small linked list in each bucket.

Key takeaways

  • A linked list is a chain of nodes. Each holds a value and a pointer to the next.
  • Inserting and removing change a couple of pointers. Reaching a position means walking to it.
  • Reversing a list turns each arrow around. No node moves.
  • Always save the next node before changing an arrow.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress