Removing Nodes from a Linked List

Traversal moves through a linked list by following next pointers from the head until null is reached.

Programming

Interactive lab

Try it: Linked List

How a singly linked list stores values in separate nodes joined by next pointers, and how inserting or deleting only rewires pointers.

How it works

HEAD points at the first node; each node holds a value and a pointer to the next node; the last node points to NULL.
To insert, create a node, store its value, point it at its successor, then point its predecessor (or HEAD) at it.
To delete, walk to the node and make its predecessor skip over it.
Searching means following next pointers from HEAD until the value or NULL is reached.

Default run (9 steps): HEAD → 10 → 20 → 30 → NULL. 3 of 10 nodes. Choose an operation. Example: append 40. … Done: HEAD → 10 → 20 → 30 → 40 → NULL.

Educational simulation

Loading the simulation…

A Tempting Way to Print Every Item

Suppose you need to print every item in a linked list. A natural first attempt is to use the head variable itself as the moving pointer: keep stepping head forward to the next node, print the item along the way, and stop when head becomes null. The loop looks clean and seems to do exactly what you want. This lesson explains why that approach is a misconception, and what to do instead.

What do you think happens?

Imagine the head variable has been used as the walking pointer, so head moves forward one node at a time until it reaches the end of the list. Once the loop finishes, what can you still reach?

Reveal answer

Answer:

Nothing. head has moved past the last node and is null, so the program has no way to reach the front of the list or any of its nodes afterward.

The head variable is the program's only doorway into the list. Once it has been moved, the way back to the first node is gone.

Why head Must Stay Put

The head variable is the program's only doorway into the list. Every operation that needs the list, including traversal, starts from that doorway. If the doorway itself is moved, the way back to the front of the list disappears. The core correction is that head must keep pointing to the first node for the whole time the list is in use, so the walking must be done with a different variable.

The standard solution is a second variable, often called a runner. It begins as a copy of head, so both variables refer to the same first node. Only the runner is allowed to move. head stays fixed on the first node, and the program can always start a new walk from it.

When the walk starts, head and runner both refer to the first node. What happens to each variable when only the runner moves?

Read the diagram carefully. Both variables point at node A, but they are not the same variable. Moving runner changes only runner. head still refers to A, and that is what keeps the whole list reachable.

Walking the List with a Runner

The standard approach has three moving parts. First, a runner variable receives a copy of head, so both variables refer to the first node at the start. Second, the loop repeatedly processes the item in the node that runner currently refers to. Third, at the end of each pass, runner is advanced by following its next pointer, so it refers to the following node. The loop stops when runner becomes null, which marks the end of the list.

java

class Node {
    String data;
    Node next;
}

class ListPrinter {
    static void printAll(Node head) {
        Node runner = head;
        while (runner != null) {
            System.out.println(runner.data);
            runner = runner.next;
        }
    }
}

class Node {
    String data;
    Node next;
}

class ListPrinter {
    static void printAll(Node head) {
        Node runner = head;
        while (runner != null) {
            System.out.println(runner.data);
            runner = runner.next;
        }
    }
}

Walk through it

1
The Node class holds the item in data and a reference to the following node in next.
2
printAll receives head, which is the program's only way into the list.
3
runner is assigned head, so it refers to the first node while head keeps its value.
4
The while condition checks runner against null before each pass.
5
Inside the loop, the item in the node that runner refers to is printed.
6
The last statement advances runner along the next pointer, so the next pass handles the following node.

Notes on the code

head is passed in and never reassigned inside printAll
runner starts as a copy of head, pointing at the first node
the loop condition tests runner for null
runner moves forward by following its next pointer

Output

A
B
C

The output assumes a list whose three nodes hold the strings A, B, and C in that order. The loop visits the nodes in list order, so the strings print in the same order they appear in the list.

On each pass the runner refers to a different node. In what order does the loop visit the nodes, and when does it stop?

Follow the trace from the top. The runner visits A, then B, then C, moving one node at a time. When it has passed C, the next pointer of C is null, so runner becomes null and the loop condition fails. The loop ends at the moment runner reaches null, not earlier.

Watching head Stay Put During the Loop

Compare the correct loop with the tempting version. The two differ only in which variable is advanced. In the tempting version, head itself is the walker, so the loop leaves head holding null when it finishes.

Before

static void printAll(Node head) {
    while (head != null) {
        System.out.println(head.data);
        head = head.next;
    }
    // head is now null: the list is unreachable through it
}

head walks the list and ends as null

After

static void printAll(Node head) {
    Node runner = head;
    while (runner != null) {
        System.out.println(runner.data);
        runner = runner.next;
    }
    // head still refers to the first node
}

runner walks the list and ends as null, while head still refers to the first node

If head is moved forward during the walk, where does the original start of the list go, and which nodes can still be reached?

In the after column the nodes A, B, and C still exist and are still linked by their next pointers, but no variable in the program refers to A anymore. The list has not been deleted; it has become unreachable. This is why the head variable must never be the one that moves.

Worked example

Tracing the runner through a three-node list

A list holds A, B, and C, with head referring to A. Trace printAll and state the value of head and runner after each pass.

1
Start
runner is assigned head, so runner refers to A. head still refers to A.
2
Pass 1
runner is not null, so the loop body runs and prints A. runner moves to B.
3
Pass 2
runner refers to B, which is not null, so B is printed. runner moves to C.
4
Pass 3
runner refers to C, so C is printed. runner moves to null because C has no following node.
5
Check
runner is null, so the condition fails and the loop ends. head still refers to A throughout.

Result

The output is A, B, C. head was never changed and still refers to the first node when the method returns.

Mistakes When Walking a List

Common mistake
Using head as the moving pointer
What it looks like
```
while (head != null) { print(head.data); head = head.next; }
```
Why it fails
Each pass moves head forward, so when the loop ends head is null and the program has no remaining path to the front of the list.
Do this instead
Copy head into a runner variable and advance only the runner.
Common mistake
Assuming the loop is finished when head is null
Why it fails
head being null after a walk only means the walker ran off the end. The nodes are still there, but they can no longer be reached through head.
Do this instead
Keep head fixed on the first node for the whole time the list is in use.
Common mistake
Testing the wrong variable in the loop condition
Why it fails
The loop must stop when the node being visited runs out, so the condition belongs on the runner.
Do this instead
Write the condition as runner != null and advance runner inside the body.

Empty Lists Need No Special Branch

An empty list is represented by a null head pointer. The traversal loop needs no special branch for this case. runner starts as null, so the loop condition is false on its first check and the body never executes. Nothing is dereferenced, so no error occurs. The same printAll method handles an empty list and a list of any length.

Edge case

Calling printAll with a null head prints nothing and returns normally. There is no if-statement guarding the loop, because the condition runner != null already does that job on the very first check.

Practice Tracing a Traversal

EASY

A list holds the strings X, Y, Y, and Z in that order. Using the runner-based printAll method, state exactly what is printed, then state the value of head after the method returns. Explain in one sentence why head is still usable afterward.

Hints

Trace runner through each node, one pass at a time.
Ask which variable is ever assigned a new value inside the loop.
Remember that the loop ends when runner becomes null.

Your attempt (not saved)

Key Takeaways

The head variable is the only access to a linked list, so it must keep pointing to the first node while the list is in use.
A runner variable copied from head is the moving pointer: it processes the current node, then follows next until it reaches null.
Advancing head during a walk leaves the list with no way to reach it afterward, even though the nodes still exist.
An empty list has a null head, so the runner loop fails its first check and runs with no special branch.