Debugging lab: pointer bugs in Python lists

Why this matters

Most linked-list code is short. The hard part is that a single wrong line can lose nodes, crash the program or make a list loop forever, and the code can still look right when you read it quickly. Reading a list function and imagining it works is not enough. You need a way to find the mistake, prove it, and fix it.

This lab gives you seven broken functions. Each one has one pointer bug. A pointer bug is a mistake about which node a link points at. For each bug you will do four things: run the broken code and see the symptom, name the bug, dry-run the code by hand on a small list, and read the fix. The earlier lessons in this module covered how to add, remove and reverse nodes. This lesson does not teach those ideas again. It teaches you how to find out why a working idea went wrong.

The tools for this lab

Every bug uses the same small Node class. A node has a val and a next, which is a link to another node. The last node has next set to None, Python's word for "no node here".

Two helper functions make the lab easier to read. build creates a list from numbers. show turns a list into text. show stops after eight nodes, so a list that loops does not print forever.

build(1, 2, 3) returns the head of the list 1 -> 2 -> 3 -> None. The *values in build means "any number of arguments". Python collects them into a tuple, which is a fixed sequence.

The show helper collects text pieces in a list and joins them with " -> ". In Java, the same job is done with a StringBuilder.

The outputs in this lab come from one run of the scripts on Python 3.14.4. Error messages can differ on other Python versions, but the bugs and the fixes stay the same. File names and line numbers in the tracebacks also depend on your files, so yours may differ.

A method for finding pointer bugs

Before you start the bugs, learn the method you will use for each one. It has four steps.

1. Run the function on a small list, usually three nodes. Look at the output or the exception.
2. Draw the list. Write each node as a box with its value and an arrow for next. Mark the variables head, cur, prev and any others with arrows showing what they point to.
3. Dry-run the function. A dry run means you trace the code by hand, one line at a time, and write down the state of every variable after each line. Use a table with one row per step. Do not skip rows. Most bugs show up in one specific row.
4. Name the bug in one sentence, then fix it. Naming the bug forces you to say what the code believes is true and what is actually true.

A dry run is only as good as the picture you draw. Keep the picture small. Three nodes are enough for every bug in this lab.

Bug 1: the loop stops one step too late

The first function adds a node at the end of a list. The rule for "add at the end" is to walk to the last node and link it to the new node. The last node is the one whose next is None.

def add_last_broken(head, v):
    cur = head
    while cur is not None:
        cur = cur.next
    cur.next = Node(v)

Run it on a list of three nodes.

a = build(1, 2, 3)
add_last_broken(a, 4)

The output is an exception. Here is the traceback from one run, with the folder part of each file path removed.

Traceback (most recent call last):
  File "tb_bug1.py", line 4, in <module>
    add_last_broken(a, 4)
    ~~~~~~~~~~~~~~~^^^^^^
  File "lab16.py", line 40, in add_last_broken
    cur.next = Node(v)
    ^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next' and no __dict__ for setting new attributes

The traceback names the line that failed and marks the part of it that caused the error with ^ signs. The last line is the message. NoneType is the type of None. The message says that the code tried to set next on None, and None is not a node, so it has no place to store a link. An AttributeError is Python's error for "this object has no such attribute".

Dry-run it on 1 -> 2 -> 3 -> None.

The bug: the loop condition checks cur, but it should check cur.next. The loop must stop on the last node, not one step after it.

The fix checks cur.next:

def add_last(head, v):
    cur = head
    while cur.next is not None:
        cur = cur.next
    cur.next = Node(v)

Dry-run the fixed version on the same list. At step 3, cur is node 3 and cur.next is None, so the loop stops with cur on node 3. Then cur.next = Node(4) links node 3 to the new node. The result is 1 -> 2 -> 3 -> 4 -> None.

This fixed version does not work on an empty list. If head is None, then cur.next raises an AttributeError when the loop starts. Add an if head is None check before the loop to handle that case.

Bug 2: insertion after a node drops the rest of the list

The second function inserts a new node right after a node that you already have. It is the same idea as the "add at the front" section of the singly linked list lesson, but the new node goes in the middle.

def insert_after_broken(node, v):
    node.next = Node(v)

Start with 1 -> 2 -> 3 -> None and insert 9 after node 1.

c = build(1, 2, 3)
insert_after_broken(c, 9)
print("broken: " + show(c))

The program prints this:

broken: 1 -> 9 -> None

Nodes 2 and 3 are gone from the list. The code replaced node.next, which was the only reference to node 2, with a reference to the new node. Nothing points at node 2 anymore, so Python frees the memory of nodes 2 and 3. Python frees an object once no name or link refers to it.

The bug is that the code overwrote next before it saved the old value. The rule from the singly linked list lesson applies again: save the reference you are about to overwrite.

def insert_after(node, v):
    n = Node(v)
    n.next = node.next
    node.next = n

The new node first takes the old next, which is node 2. Only after that does node.next point to the new node. The order matters. Swapping the last two lines makes n.next point to itself.

Run the fixed version on the same list.

d = build(1, 2, 3)
insert_after(d, 9)
print("fixed:  " + show(d))

fixed:  1 -> 9 -> 2 -> 3 -> None

Bug 3: removing the head is not handled

The third function removes the first node that has a given value. Finding the node is easy. Unlinking it needs the node before it, called prev, because you must change prev.next. When the node to remove is the head, there is no node before it.

def remove_broken(head, target):
    prev = None
    cur = head
    while cur is not None and cur.val != target:
        prev = cur
        cur = cur.next
    if cur is None:
        return head
    prev.next = cur.next
    return head

Run it to remove the value 4 from 4 -> 5 -> 6 -> None.

remove_broken(build(4, 5, 6), 4)

AttributeError: 'NoneType' object has no attribute 'next' and no __dict__ for setting new attributes

Dry-run it. The loop stops at the first node, because cur.val is 4 and target is 4. So prev is still None, which is its starting value, and cur is node 4. The code then runs prev.next = cur.next, which sets an attribute on None. That is the crash.

The bug: the code assumes there is always a node before the target. The head has none, so prev is None.

The fix handles that one case before the normal unlink:

def remove(head, target):
    prev = None
    cur = head
    while cur is not None and cur.val != target:
        prev = cur
        cur = cur.next
    if cur is None:
        return head
    if prev is None:
        return cur.next
    prev.next = cur.next
    return head

When prev is None, the target is the head, so the new head is the node after it. The function returns that node. The caller must use the return value, because the head itself has changed. An unlink that returns head unchanged would keep the removed node at the front.

The fixed code gives these results:

fixed, remove 4: 5 -> 6 -> None
fixed, remove 5: 4 -> 6 -> None

The second line shows the normal case. Node 5 has a node before it, so prev is node 4 and the code runs prev.next = cur.next.

Bug 4: is compares objects, not values

The fourth function checks whether a value is in a list. The function uses is where it should use ==. The two operators look alike but test different things.

• == asks whether two values are equal.
• is asks whether two names point at the same object.

def contains_broken(head, target):
    cur = head
    while cur is not None:
        if cur.val is target:
            return True
        cur = cur.next
    return False

The test builds one node for each value. The values are made with int("100") and int("1000"), which is explained below.

small = build(int("100"))
t1 = int("100")
print("broken, 100 in list:", contains_broken(small, t1))
 
big = build(int("1000"))
t2 = int("1000")
print("broken, 1000 in list:", contains_broken(big, t2))

broken, 100 in list: True
broken, 1000 in list: False

The value 1000 is in the list, but the function says it is not. The is check compares the two objects. The number 100 is found because CPython, the standard Python program, keeps one shared object for small whole numbers. Each int("1000") call makes a new object, so the two objects are different even though the numbers match.

Java programmers may remember a similar trap with Integer objects. Python has no separate boxed type, but the same test failure happens with is.

The range of shared small numbers is a detail of CPython, and it is not a rule of the language. A check on Python 3.14.4 showed that -5 and 256 are shared, and -6 and 257 are not. Other Python versions may use a different range, so a program must never depend on it.

This bug is very common, and it is hard to see, because the code works for small numbers. A test with only small numbers passes.

The fix compares the values with ==:

def contains(head, target):
    cur = head
    while cur is not None:
        if cur.val == target:
            return True
        cur = cur.next
    return False

The check against None in while cur is not None still uses is, because the question there is about the missing node itself, not about a value.

print("fixed, 1000 in list:", contains(big, t2))

fixed, 1000 in list: True

The int("1000") calls matter for the test. Two equal literals written in the same piece of code can be the same object. A run of p = 1000 and q = 1000 in one script printed p is q as True. Calling int("1000") each time makes two separate objects, so the test shows the bug.

A dry run shows the bug in one row. At the first comparison, cur.val and target are two different objects with the same number. The is check gives False, and the loop moves on.

Bug 5: reversal overwrites next before it is saved

The fifth function reverses a list in place, so the last node becomes the first. Each node's next must point to the node before it. The problem is the order of operations inside the loop.

def reverse_broken(head):
    prev = None
    cur = head
    while cur is not None:
        cur.next = prev
        prev = cur
        cur = cur.next
    return prev

Run it on 1 -> 2 -> 3 -> None:

print("broken: " + show(reverse_broken(build(1, 2, 3))))

broken: 1 -> None

Dry-run it. Write the state after each line.

The loop stops after one step. Node 2 and node 3 are no longer reachable from node 1, because the line cur.next = prev replaced the only reference that led to node 2. Then the line cur = cur.next read the new value of next, not the old one. The code wanted to move to node 2, but it moved to the value it had just written.

The fix saves the old next in a new variable before you change it:

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

The name nxt holds the rest of the list while cur.next is changed. Then cur moves to the saved value.

fixed:  3 -> 2 -> 1 -> None

Python can also write the three assignments on one line, cur.next, prev, cur = prev, cur, cur.next. Python evaluates the right side first, so the old cur.next is read before anything changes. The one-line form works, but the three-line form is easier to dry-run, so this lesson uses it.

This is the same rule as bug 2. Save the reference first, then change the link.

Bug 6: the first part is not cut from the second part

The sixth function splits a list into two lists. The first list has the first k nodes. The second list has the rest. To split, you must make the last node of the first list point to None. If you do not, the first list still runs into the second list.

def split_broken(head, k):
    cur = head
    for _ in range(k - 1):
        if cur is None:
            break
        cur = cur.next
    second = None if cur is None else cur.next
    return head, second

The function returns a tuple with two items. The first item is the head of the first part, and the second item is the head of the second part. Run it on 1 -> 2 -> 3 -> 4 -> None with k = 2.

halves = split_broken(build(1, 2, 3, 4), 2)
print("broken first part: " + show(halves[0]))
print("broken second part: " + show(halves[1]))

broken first part: 1 -> 2 -> 3 -> 4 -> None
broken second part: 3 -> 4 -> None

The first part should be 1 -> 2 -> None. Instead it contains the whole list. The two parts share nodes 3 and 4, so a change to one part changes the other.

The bug is that the code found the cut point, saved the second part, but did not cut. The fix sets the cut point's next to None after saving the second part.

def split(head, k):
    cur = head
    for _ in range(k - 1):
        if cur is None:
            break
        cur = cur.next
    if cur is None:
        return head, None
    second = cur.next
    cur.next = None
    return head, second

The check if cur is None handles a list shorter than k. In that case there is nothing to cut. Python lets the caller unpack the tuple into two names, as this run shows:

first, second = split(build(1, 2, 3, 4), 2)
print("fixed first part: " + show(first))
print("fixed second part: " + show(second))

fixed first part: 1 -> 2 -> None
fixed second part: 3 -> 4 -> None

Notice that the second part is not changed by the fix. The bug is only in the first part's end.

Bug 7: rotation makes a loop

The last function moves the last node to the front of the list. This is one rotation. For 1 -> 2 -> 3 -> None, one rotation gives 3 -> 1 -> 2 -> None.

def rotate_once_broken(head):
    if head is None or head.next is None:
        return head
    prev = None
    cur = head
    while cur.next is not None:
        prev = cur
        cur = cur.next
    cur.next = head
    return cur

The loop walks to the last node. prev is the node before it, and cur is the last node. The code makes cur.next point to the old head. That part is correct. The missing line is prev.next = None, which removes the old link from the second-last node to the last node.

Run it:

print("broken: " + show(rotate_once_broken(build(1, 2, 3))))

broken: 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> ... (still going after 8 nodes)

The list never ends. This is a loop. The show helper stops after eight nodes because of the loop, and it says so.

Dry-run the links. Before the function runs, the list is 1 -> 2 -> 3 -> None. After cur.next = head, node 3 points to node 1. Node 2 still points to node 3, because nothing changed prev.next. So the links are:

• node 3 points to node 1
• node 1 points to node 2
• node 2 points to node 3

That closed circle is the loop. The bug: the function made the last node point to the head, but it did not remove the old link to the last node.

The fix adds the missing line:

def rotate_once(head):
    if head is None or head.next is None:
        return head
    prev = None
    cur = head
    while cur.next is not None:
        prev = cur
        cur = cur.next
    prev.next = None
    cur.next = head
    return cur

fixed:  3 -> 1 -> 2 -> None

Now the new head is node 3, whose next leads to node 1, then node 2, then None.

Common mistakes

These are mistakes that appear when you debug the lab, or when you write your own list code after it.

Reading the error message as a variable name

The messages in bugs 1 and 3 name the attribute that failed, next, and the type of the object, NoneType. They do not name the variable. To find the variable, read the line that the traceback shows and find the name that holds None. The ^ marks under the line show the part that failed.

The message has two forms. Setting an attribute on None, as in bugs 1 and 3, adds the words and no __dict__ for setting new attributes. Reading an attribute on None gives the shorter message, as in exercise 1 below.

Reading the loop condition as "the node I am on"

Bug 1 comes from a loop condition that checks the wrong node. A loop that stops on cur is not None ends after the last node, not on it. When you write a loop that walks a list, ask: what should cur be when the loop ends? Then write the condition that gives that value.

Forgetting that a function can change the head

Bug 3 and bug 7 both return a new head. If you call remove_broken(lst, 4) and then keep using the old lst variable, the code uses a head that may no longer be first. Use the returned value.

Printing a list that loops

If a list loops, a print inside a while loop runs forever. Your terminal shows the same text repeating until you stop the program. Press Ctrl+C to stop it. Python does not detect the loop for you. Use a counter, like the one in show, when you print a list you do not fully trust.

Believing a test that passes for small values

Bug 4 passes for 100 and fails for 1000. A test with only small numbers would say the code works. Test with values on both sides of the common boundaries: small values, values around 256, and large values. Remember that the is check can pass by accident for small numbers, so use == for values and is only for None.

Changing a link before saving the old one

Bugs 2 and 5 are the same mistake. Any time you write a.next = something, ask whether you still need the old a.next. If you do, save it in a variable first.

Practice

Use the code from this lesson in your own scratch file. Write the answer before you check it. Each answer has a short explanation.

Exercise 1: find the missing node

This function is meant to print every value in a list. It is wrong for two inputs. Find both.

def print_all(head):
    cur = head
    while cur.next is not None:
        print(cur.val)
        cur = cur.next

Run it on build(1, 2, 3) and on None. Explain each output.

Show the answer

On build(1, 2, 3) it prints 1 and 2. The loop stops when cur is node 3, because cur.next is None, so node 3 is never printed. On None the first line of the loop reads cur.next, which is an attribute of None, so the program raises AttributeError: 'NoneType' object has no attribute 'next'. The fix is while cur is not None, which prints every node and handles the empty list without a special case.

Exercise 2: predict the output

Predict the output of this code, then check it.

a = build(7, 8, 9)
b = a
a.next = b.next.next
print(show(a))

Show the answer

The output is 7 -> 9 -> None. The names a and b point to the same node, so b.next.next is node 9. Then a.next points to node 9, and node 8 is no longer in the list. This is an example of two names for one node. Changing a node through one name is visible through the other.

Exercise 3: the caller does not see the new head

This function swaps the first two nodes. It is wrong because the caller keeps the old head.

def swap_first_two(head):
    first = head
    second = head.next
    first.next = second.next
    second.next = first

Run it on build(1, 2, 3), then print the list from the old head. Explain the output, then write the fix.

Show the answer

Printing from the old head gives 1 -> 3 -> None. Node 1 is still the name head, but it is now the last node. The new first node is node 2, which the caller never receives. The fix returns second, and the caller uses the returned value:

def swap_first_two(head):
    if head is None or head.next is None:
        return head
    first = head
    second = head.next
    first.next = second.next
    second.next = first
    return second

With this fix, the result from build(1, 2, 3) is 2 -> 1 -> 3 -> None.

Exercise 4: detect a loop with a limit

Write def has_loop_within(head, limit). It walks at most limit steps. It returns True if it is still on a node after those steps, which means the list is longer than limit or it loops. Test it on build(1, 2, 3) with limit 5, and on a list whose last node points back to the head.

Show the answer

def has_loop_within(head, limit):
    cur = head
    for _ in range(limit):
        if cur is None:
            break
        cur = cur.next
    return cur is not None

For build(1, 2, 3) with limit 5, the loop reaches None after three steps, so the result is False. For a loop with limit 5, the walk never reaches None, so the result is True. This test does not say whether the list has a loop. It says only that the list is more than limit nodes long or never ends. Finding a loop exactly needs a different method, which is not part of this lab.

Exercise 5: why 256 and 257 behave differently

Predict the output of this code, then explain it in one sentence.

x1 = int("256")
x2 = int("256")
y1 = int("257")
y2 = int("257")
print(x1 is x2)
print(y1 is y2)
print(y1 == y2)

Show the answer

The output is True, False, True. In CPython, 256 is one of the small numbers that share one object, so both names point to the same object. For 257, each int("257") call makes a new object, so is compares two different objects. The == check compares the numbers, so it returns True. The boundary of 256 is a CPython detail, and a program must not depend on it.

Summary

• A pointer bug is usually a change to next in the wrong order, or a loop that stops on the wrong node.
• Draw the list and dry-run the code on three nodes before you change anything.
• Save an old reference in a variable before you overwrite it.
• Handle the head as a special case when a function changes the first node.
• Use == to compare values and is to compare with None or to check that two names share one object.
• A list that loops does not crash by itself, so print it with a limit when you are not sure.