Traversing a Linked List with a Loop

A non-empty linked list splits into a head node and a tail, and the tail is itself a shorter linked list.

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…

Walking a List Without a Loop

A linked list is usually processed with a loop. You start at the first node, move through each next reference, and stop when you reach null. This article asks a different question: how can a recursive method work through a list one node at a time without a loop at all? Recursion is rarely the most natural tool for this job, but learning it pays off, because the same reasoning carries over to recursive processing of more complex data structures such as trees, where a loop is less convenient.

What do you think happens?

Given a list with the values 4, 7, and 2 in that order, what total does a method that adds up every value in the list return?

Reveal answer

Answer:

4 + 7 + 2 = 13. The rest of this article shows how a recursive method reaches that total by handling one head at a time and delegating the tail.

Splitting a List into Head and Tail

A non-empty linked list splits into two parts: a head node and a tail. The head is the first node. The tail is everything that remains after it. The important point is that the tail is not some different kind of object. It is itself a linked list, and it is shorter than the original by exactly one node.

How does a list of nodes break into one head node plus a shorter list that is still a linked list, and what does the tail point to?

In the diagram, Node 4 is the head. Following its next reference leads to Node 7, and the nodes from Node 7 onward form the tail. The tail is a list of two nodes sitting inside the original list of three. That is the structure the recursive method depends on: a list contains a smaller list inside it.

Why head.next Gives the Tail

If the variable head refers to the first node, then head.next refers to the second node. That second node is the first node of the tail. So head.next works as a reference to the tail of the list. You do not need a separate operation to obtain the tail. Following one reference gives you everything that remains.

Consider the case where the list has only one node. Its tail contains nothing, so head.next is null. An empty list is represented by a null reference, which means head.next still represents the tail even in this special case. The same expression works for every non-empty list, including the shortest one. This consistency is what lets one method handle every size without a special branch for the single-node case.

The Summing Algorithm in Plain Steps

The source develops a recursive algorithm for adding up the integers in a linked list. The algorithm has two cases. The base case handles the empty list, and the recursive case handles every non-empty list. Written in plain steps, the algorithm works like this.

1
Check whether the list is empty. If it is, return 0, because there are no numbers to add. This is the base case.
2
Otherwise, take the number stored in the head node.
3
Find the sum of the tail by calling the same method on head.next. This is the recursive case.
4
Add the head number to the sum returned by the tail call, and return that total.

Key point

The base case returns a neutral value for the empty list, which is 0 for a sum. The recursive case combines the head item with the result for the tail. Both cases are needed: without the base case the calls would never stop, and without the recursive case the method could only ever see one node.

Writing the Sum Method in Code

The code below is an illustrative translation of the plain-step algorithm into Python. It assumes each node has a value and a next reference, with None representing the null reference at the end of the list. Read it as the two cases in order: the empty-list check first, then the head-plus-tail line.

python

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

def list_sum(head):
    if head is None:
        return 0
    return head.value + list_sum(head.next)

# Build the list 4 -> 7 -> 2
three = Node(2)
two = Node(7, three)
first = Node(4, two)
print(list_sum(first))

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

def list_sum(head):
    if head is None:
        return 0
    return head.value + list_sum(head.next)

# Build the list 4 -> 7 -> 2
three = Node(2)
two = Node(7, three)
first = Node(4, two)
print(list_sum(first))

Output (expected)

Notes on the code

head is None is the base case: an empty list returns 0
head.value is the item handled directly at this call
list_sum(head.next) delegates the tail to a fresh call of the same method
The + combines the head value with the value returned by the tail call

Code walkthrough

def list_sum(head):
    if head is None:
        return 0
    return head.value + list_sum(head.next)

1
The first line defines the method, which receives the head node of whatever list it is given.
2
The if statement checks for the empty list. Since an empty list is a null reference, head is None is true exactly when there is nothing left to add.
3
The return 0 line is the base case. It returns the neutral value for a sum.
4
The final return line is the recursive case. It reads the head value, calls list_sum on head.next, and adds the two results before returning.

Tracing the Calls Down and Back Up

Recursion has two phases. During descent, each call hands a smaller list downward. During unwinding, control returns upward and the addition happens. Each recursive call must wait for the call it made to return before it can finish its own addition. While the descent is in progress, the earlier calls are paused, and each one remembers which head item it still needs to add.

What is on the call stack at each step as sum(head) delegates to sum(tail), and when does the chain of pending calls start to resolve?

Read the diagram from the top. The first call is the outermost one, and it is the last to finish. The empty list at the bottom is the deepest call, and it is the first to finish. Each call above it is waiting for a single value to come back, which is the tail sum it asked for.

Worked example

Unwinding the sum of 4, 7, 2

Trace list_sum on the list 4 -> 7 -> 2, showing the value each call returns.

1
Descent
sum of 4, 7, 2 calls sum of 7, 2, which calls sum of 2, which calls sum of empty list.
2
Base case
sum of empty list returns 0 without making any further call.
3
First unwind
sum of 2 receives 0, adds its head 2, and returns 2.
4
Second unwind
sum of 7, 2 receives 2, adds its head 7, and returns 9.
5
Final unwind
sum of 4, 7, 2 receives 9, adds its head 4, and returns 13.

Result

The method returns 13, the total of all three values.

Unwinding explains why the recursive case must use the value returned by the call. The deepest call resumes first, adds its own head item to the tail sum it just received, and returns that total to the call that is waiting for it. Each resumed call does the same, so the contribution of every node travels back up to the top.

Where a Result Goes Wrong

Tracing the calls shows exactly where a recursive sum can fail. The unwinding phase is where the actual addition happens, so a mistake at that point changes the final answer. The two most common errors are shown below.

Common mistake
Computing the tail sum but ignoring its returned value
What it looks like
return head.value when the tail call is made but its result is discarded
Why it fails
If the recursive case computes the tail sum and then ignores it, the result is just the head item. The returned value is what carries the contribution of the rest of the list back up to the top.
Do this instead
Add the returned value to head.value, as in return head.value + list_sum(head.next).
Common mistake
Returning the wrong neutral value from the base case
What it looks like
```
if head is None: return 1
```
Why it fails
The base case must return the neutral value for the operation. For a sum that is 0. Returning 1 adds an extra value to every total, because the empty tail contributes to each unwinding step.
Do this instead
Return 0 for the empty list when computing a sum.
Common mistake
Omitting the base case, so the calls never reach an empty list and the recursion does not stop

Before

def list_sum(head):
    if head is None:
        return 0
    list_sum(head.next)
    return head.value

The tail sum is computed and then thrown away, so list 4 -> 7 -> 2 returns 4.

After

def list_sum(head):
    if head is None:
        return 0
    return head.value + list_sum(head.next)

The tail sum is added to the head value, so list 4 -> 7 -> 2 returns 13.

Loop Versus Recursion

A loop and a recursive method both visit every node, but they organise the work differently. A loop keeps one pointer that moves forward through the list, updating a running total at each step. A recursive method does not move a pointer. Instead, each call handles its own head directly and gives the tail to a new call, and the totals are combined on the way back up.

How does a loop that moves a pointer forward differ from recursion that delegates the tail, in terms of what changes at each step and what gets accumulated?

Aspect	Loop traversal	Recursive traversal
Movement through the list	A pointer moves forward through next references	No pointer moves; each call receives head.next
Accumulation	A running total is updated at each step	Each call adds its head value to the value returned by the tail call
Stopping condition	Stop when the pointer reaches null	Base case returns the neutral value when head is None
Where the addition happens	During the forward pass	During unwinding, as calls return
Natural fit	Usually the most natural tool for a linked list	Useful reasoning that carries over to trees and more complex structures

Two ways to visit every node of a linked list

Practice Tracing a Short List

EASY

A two-node list holds the value 5 in its head node and the value 1 in the node after it. Trace list_sum on this list. List each call, its base case or recursive case, and the value it returns. Then state the final result.

Hints

Start with the outermost call on the head node holding 5, and write down which case it takes.
The tail of this list is a one-node list. Its own tail is empty, so one more call reaches the base case.
During unwinding, add the head value of each call to the value it received from the call below it.

Your attempt (not saved)

Key Takeaways

A non-empty linked list splits into a head node and a tail, and the tail is itself a shorter linked list, one node smaller than the original.
head.next refers to the tail, and it is null for a single-node list, so one method handles every list size.
A recursive sum has a base case that returns 0 for the empty list and a recursive case that adds the head value to the result for the tail.
Results are built during unwinding, when each waiting call adds its head value to the value it received; ignoring the returned value collapses the result to the head alone.
A loop is usually the natural way to traverse a linked list, while the recursive head-and-tail reasoning carries over to trees.