Traversing a Singly Linked List

Number 2 stops early. Testing while walk.data instead of while walk is not None works on most data and then silently stops at the first empty string, zero or None in the list. Test the node, never the value inside it.

Number 3 skips the first node. Advancing before using visits nodes 2 to n. It is easy to write when converting a for loop out of habit.

What traversal costs

One visit per node, so n steps for n nodes: O(n), and there is no faster way. A linked list has no shortcut to the middle, so anything that needs to see the whole list costs a full walk.

That is worth stating plainly because it is the source of several later results. length is O(n). append without a tail pointer is O(n). Reaching item i is O(n). All three are the same walk.

Traversing with an index, and why it is a trap

Students who learned arrays first sometimes write this:

If item_at(i) walks from the head, that loop is not O(n). It is O(n squared): the first item costs 1 step, the second 2, the last n, and the total is about n squared over 2. On a list of 10,000 that is about 50 million steps to do what a single traversal does in 10,000.

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


def build(n):
    head = None
    for value in reversed(range(n)):
        head = Node(value, head)
    return head


def item_at(head, i):
    """Walk to item i. Returns (value, steps)."""
    walk, steps = head, 0
    while i > 0:
        walk = walk.next
        steps += 1
        i -= 1
    return walk.data, steps


def by_traversal(head):
    steps, walk = 0, head
    while walk is not None:
        steps += 1
        walk = walk.next
    return steps


def by_index(head, n):
    total = 0
    for i in range(n):
        _, steps = item_at(head, i)
        total += steps + 1
    return total


for n in (250, 500, 1000, 2000):
    head = build(n)
    print("n = %4d   one traversal: %5d steps   indexed loop: %8d steps"
          % (n, by_traversal(head), by_index(head, n)))

n =  250   one traversal:   250 steps   indexed loop:    31375 steps
n =  500   one traversal:   500 steps   indexed loop:   125250 steps
n = 1000   one traversal:  1000 steps   indexed loop:   500500 steps
n = 2000   one traversal:  2000 steps   indexed loop:  2001000 steps

Read the right column down: the data doubles and the work goes up four times. That is the signature of O(n squared), and it comes from writing an array's loop over a linked structure.

Quick revision

• Traversal: walk = head, then while walk is not null, use walk.data and walk = walk.next.
• Every linked list algorithm is that shape with something added.
• The empty list needs no special case: the loop never runs.
• Three classic errors: forgetting to advance (hangs for ever), testing walk.data instead of the node

(stops at the first falsy value), advancing before using (skips the first node).

• Traversal is O(n) and there is no shortcut, which is why length, append without a tail, and access by

index are all O(n).

• Looping by index over a linked list is O(n squared): doubling the data quadrupled the work in the run

above.

Test yourself

1. Write the traversal pattern in three lines. walk = head; while walk is not null: use walk.data; walk = walk.next.

2. Why does a correct traversal need no special case for the empty list? Because head is null, so the loop condition fails immediately and the body never runs.

3. What happens if walk = walk.next is omitted, and why is that worse than a crash? The loop never ends. It hangs rather than failing, so there is no error message and no line number to look at.

4. Why test walk is not None rather than walk.data? Because a node may legitimately hold an empty string, a zero or None, and testing the data would stop the traversal at that node instead of at the end of the list.

5. A loop calls item_at(i) for i from 0 to n-1. What is its cost, and why? O(n squared), because each item_at walks from the head: 1 step, then 2, up to n, which totals about n squared over 2.

6. In the run above, n doubled from 1000 to 2000. What happened to the indexed loop's steps? They went from about 500,000 to about 2,000,000, four times as many, which is the signature of O(n squared).