Drawing reference diagrams for Python lists

Why this matters

Most bugs in linked structures come from a wrong guess about which arrow points where. A programmer reads a line such as head.next = head.next.next and imagines the list changing. The imagined list is often not the real one. A few minutes of drawing before running the code catches the wrong guess, and it is faster than adding print statements after each line.

This lesson teaches a drawing method. You draw one box for each object, and one label for each name. You draw one arrow for each reference. Then you change the drawing one line at a time, the same way the code changes the program. The drawing predicts what the code will print, and you check the prediction by running the code.

The lesson uses a Python linked list with a Node class. The earlier lesson on references in this module explained what a reference is. The lesson on None bugs covered what happens when an arrow points to nothing. This lesson uses both ideas and does not repeat them.

The drawing rules

Use four rules and nothing else.

1. A name is a label with an arrow coming from it. The name is not the object. Writing head names an arrow, and the arrow points to a box.
2. An object is a box. Inside the box, write its attributes. For a node in a list, that is the value and the next reference.
3. An arrow is a reference. It leaves an attribute or a name and points at one object. If a reference is None, the arrow ends in the word None and does not point at any box.
4. An assignment changes one arrow. a.next = x moves the arrow that leaves the box for a. It does not move the box for a, and it does not move the box for x.

Rule 4 is the one that causes the most mistakes. Code that looks like it moves a node usually moves only an arrow. The node stays where it is, and it stays in memory as long as some arrow still reaches it.

In the text diagrams below, a node box is written as [ value | o ]. The o marks the next reference, which is the arrow that leaves the box. A node that ends the list is written as [ value | None ]. The arrow from one box to the next is written as -->. A name sits above a short vertical line that points down at its box.

Example 1: removing the middle node

Start with a list of three nodes: 1, 2 and 3. Three names point at the three nodes. The name head points at the first node, b points at the second node, and c points at the third node.

Here is the code. The show function returns the text of a list from a given first node. It stops after 10 nodes, so a loop in the list cannot run forever.

Type nothing into the Input box for this program.

before: 1 -> 2 -> 3 -> null
after: 1 -> 3 -> null
b still points to node 2, whose next is 3

Draw the picture before you read the output. Start with the state before the removal:

head        b           c
 |          |           |
 v          v           v
[ 1 | o ]-->[ 2 | o ]-->[ 3 | None ]

The line head.next = head.next.next has two parts. The right side, head.next.next, has two dots. From head, follow the arrow to node 1. From node 1, follow its arrow to node 2, then to node 3. The right side is therefore node 3. The left side, head.next, names the arrow that leaves node 1. The assignment moves that arrow so it points at node 3.

Now draw the state after the line runs:

head
 |
 v
[ 1 | o ]------------>[ 3 | None ]
                      ^
                      |
b                     |
|                     |
v                     |
[ 2 | o ]-------------+

Node 2 is still in the drawing. Nothing points at it from head, so the list from head skips it. But b still points at node 2, and node 2 still points at node 3. The output confirms this. The program printed 1 -> 3 -> null for the list, and the last line shows that node 2 still exists with its next reference set to node 3.

In Python, the middle node is not freed when the arrow from node 1 moves away. It is freed only when no name or attribute can reach it. Here b still reaches it, so it stays. If the program later sets b = None, the only remaining path to node 2 is gone, and CPython frees it at once.

Predicting the result

The rule for a removal is to write the new arrow that skips the node, and then ask two questions. Does head still reach every node you want? Is there a name that still reaches the removed node? The second question tells you whether the removed node is still alive.

Example 2: inserting between two nodes, and the order of two lines

Inserting a node in the middle of a list takes two assignments. The order of those two lines decides whether the list survives. The drawing shows this clearly.

Start with a list 1 -> 2 -> 3, where a points at node 1. Insert a new node with the value 9 after node 1. The new node is called x. The two lines are:

x.next = a.next
a.next = x

Before the first line, a.next is the arrow to node 2. The first line copies that arrow into x. Now x points at node 2 as well. Nothing has been removed yet. The second line moves the arrow from a so that it points at x. The old arrow from a to node 2 is replaced. Node 2 is still reached, through x.

Here is the state after the first line:

a
|
v
[ 1 | o ]-->[ 2 | o ]-->[ 3 | None ]
             ^
x            |
|            |
v            |
[ 9 | o ]----+

Here is the state after the second line:

a
|
v
[ 1 | o ]-->[ 9 | o ]-->[ 2 | o ]-->[ 3 | None ]

Now reverse the order of the two lines. Set a.next = x first, then x.next = a.next. The second line reads a.next after the first line has changed it. The arrow from a now points at x, so a.next is x. The line x.next = a.next therefore makes x point at itself.

The full program below runs both versions. It uses the same Node class and show function as Example 1.

Type nothing into the Input box for this program.

correct: 1 -> 9 -> 2 -> 3 -> null
wrong: 1 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> null

In the wrong version, y.next is y. Node 9 points at itself, so the list from p never ends. The show function stopped after 10 nodes and then added -> null, as it always does, so the output looks finite. Nodes 2 and 3 still exist, because q and r point at them, but nothing reachable from p leads to them.

The drawing of the wrong version has one box that points back to itself:

[ 1 | o ]-->[ 9 | o ]-+
                      |
                      +--- node 9 points back to node 9

The rule for insertion is simple. Write the line that copies the old arrow first, then the line that moves the arrow from the node before. A drawing helps because it shows that the second line must not read an arrow that the first line has changed.

Example 3: two names for one box

A reference is a copy of an arrow. If you write alias = head, you get a second arrow that points at the same box as head. There is still one box. The two arrows are separate, and changing one of them does not change the other.

This example uses a list of three nodes. The program makes alias a second arrow to the first node, moves alias to the next node, and then changes a value through alias.

Type nothing into the Input box for this program.

before: head=1, alias=1
after alias = alias.next: head=1, alias=2
after alias.value = 100: 1 -> 100 -> 3 -> null

The first picture has two names pointing at node 1:

head   alias
 |      |
 v      v
[ 1 | o ]-->[ 2 | o ]-->[ 3 | None ]

The line alias = alias.next moves the arrow of the name alias. It does not change any node. The picture after that line:

head        alias
 |           |
 v           v
[ 1 | o ]-->[ 2 | o ]-->[ 3 | None ]

The arrow of head still points at node 1. This is why the output shows head=1 after the move.

The line alias.value = 100 changes an attribute inside a box. It does not change an arrow. The box that alias points at is node 2, so node 2 holds 100 now. Node 2 is also the box that head reaches through its next arrow, so the list from head shows 100 in the second place. The drawing made this easy to predict: a change to an attribute is visible through every arrow that reaches that box.

Example 4: reversing a list

Reversing a list is the hardest common case, because each node has to turn its arrow around before the program loses the rest of the list. The standard method uses three names. prev points at the node that has already been reversed. cur points at the node being turned now. nxt remembers the rest of the list before cur.next is changed.

Here is the function, with a list of 10, 20 and 30. The function prints a line after each step, so you can compare the output with your drawings. The name function turns a node into its value, or into the word null when the node is missing.

Type nothing into the Input box for this program.

start: 10 -> 20 -> 30 -> null
after step 1: prev=10, cur=20, reversed part: 10 -> null
after step 2: prev=20, cur=30, reversed part: 20 -> 10 -> null
after step 3: prev=30, cur=null, reversed part: 30 -> 20 -> 10 -> null
result: 30 -> 20 -> 10 -> null

Now draw the state at the start of the loop. The name prev is None, so it has no arrow. The name cur points at node 10. The three nodes still point forward:

prev            cur
 (none)          |
                 v
               [ 10 | o ]-->[ 20 | o ]-->[ 30 | None ]

The first line of the loop, nxt = cur.next, adds a new name. nxt points at node 20. This is the arrow that would be lost if the program changed cur.next without saving it.

The second line, cur.next = prev, changes the arrow of node 10. It now points at None, because prev is None in the first step. The third and fourth lines move prev to node 10 and cur to node 20. After step 1 the drawing is:

prev                 cur
 |                    |
 v                    v
[ 10 | None ]     [ 20 | o ]-->[ 30 | None ]

The output says prev=10, cur=20, and the reversed part is 10 -> null. The drawing has the same meaning. Node 10 is now the end of the reversed part, and node 20 starts the rest.

Step 2 turns node 20 around. Its arrow now points at node 10, and prev moves to node 20:

prev                      cur
 |                         |
 v                         v
[ 20 | o ]-->[ 10 | None ]  [ 30 | None ]

Step 3 turns node 30 around. Its arrow points at node 20. Then cur becomes None, and the loop stops:

prev
 |
 v
[ 30 | o ]-->[ 20 | o ]-->[ 10 | None ]

The function returns prev, which points at node 30. That is the new first node. The output prints 30 -> 20 -> 10 -> null.

The step-by-step drawing also shows why the three names are needed. Without nxt, step 1 would change the arrow of node 10 and lose the arrow to node 20. Without prev, step 2 would have no node to point back at. Each name holds one arrow that would otherwise be lost.

Common mistakes

Mistake 1: changing the arrow before saving it

The most common reversal bug is to write cur.next = prev before nxt = cur.next. Then the arrow to the rest of the list is lost, and the program keeps only the first node. Here is the version with the saving line removed:

Type nothing into the Input box for this program.

wrong reverse gives: 10 -> null
node 20 still exists with value 20, next is 30

Draw the state after the first step. cur.next = prev set the arrow of node 10 to None. Then cur = cur.next read that arrow, so cur became None, and the loop ended. Nodes 20 and 30 are still in memory, because r2 still points at node 20. They are no longer part of the list from result. The drawing shows this at once, because the arrow from node 10 to node 20 has disappeared.

Mistake 2: forgetting that a name is only an arrow

Some learners draw head as a box that holds the first node. The name is not a box that holds a node. It is an arrow. Writing head = head.next moves the arrow of head to the second node. The old first node is not changed, and it stays in memory while another arrow still reaches it.

When you draw, always make the name an arrow with a label. If you cannot say which box the arrow points at, the drawing is not finished.

Mistake 3: losing the head

When you remove or reverse the first node, the name that holds the first node must change. If the code only changes the arrows after the first node, the name still points at the old first node, which may now be the last node. The result is a list that prints too short or too long. Check the name head after each change, and draw its arrow.

Mistake 4: drawing a loop without noticing it

A list that points back to an earlier node loops. A loop does not end when the code follows the arrows. The example with y.next = y shows a one-node loop, and the show function stopped after 10 nodes. In a drawing, a loop is a path that returns to a box you have already drawn. Stop and check the arrow that closed the loop, since it is usually the line that was written last.

Practice

Exercise 1

Start with the list 1 -> 2 -> 3. The names are a for node 1, b for node 2 and c for node 3. Then run a.next = c. What does show(a) print? What is b.value, and what is b.next.value?

Show the answer

show(a) prints 1 -> 3 -> null. b.value is 2, because node 2 still exists and b still points at it. b.next.value is 3, because node 2 still points at node 3. The line a.next = c changed one arrow, the one that leaves node 1.

Exercise 2

Start with the list 1 -> 2 -> 3 and the name head for node 1. Then the code runs this:

x = head
head = head.next
x.next = None

What does show(head) print? What does show(x) print?

Show the answer

show(head) prints 2 -> 3 -> null. x points at node 1 and x.next is now None, so show(x) prints 1 -> null. Draw the three lines one at a time. The first line adds an arrow for x. The second line moves the arrow of head to node 2. The third line changes the arrow of node 1 to None. Node 1 is no longer in the list from head, but x still reaches it.

Exercise 3

Start with the list 1 -> 2 -> 3, with head at node 1. Insert a new node with value 9 at the front of the list, so the new first node is 9. Write the two lines of code and draw the arrows after each one.

Show the answer

n = Node(9, head)
head = n

The first line makes a new node whose next arrow points at node 1, so the new node already leads into the old list. The second line moves the arrow of head to the new node. The result prints 9 -> 1 -> 2 -> 3 -> null. Writing head = Node(9, head) on one line does the same thing, because Python reads the right side before it assigns head.

Exercise 4

Two names p and q both point at a node with value 5. The code runs q.value = 8. What is p.value? What would change if the code had run q = Node(8) instead?

Show the answer

p.value is 8, because p and q are two arrows to one box. The line q.value = 8 changes an attribute inside the box, and both arrows see the change. With q = Node(8), q points at a new box, and p.value stays 5. The line changed the arrow of q, not the box.

Exercise 5

Reverse the list 1 -> 2 with a function that works like reverse from Example 4, but does not print. Draw the state after the first step. Then say what the old first node's next attribute holds after the function returns.

Show the answer

After step 1, node 1 points at None, prev points at node 1, and cur points at node 2. After the function ends, the list is 2 -> 1 -> null. The old first node is node 1, which is now the last node, and its next attribute holds None. Checking old_first.next is None gives True.

Summary

• Draw a box for each object and an arrow for each reference. A name is an arrow with a label, not a box.
• An assignment such as a.next = x changes one arrow. It does not move any box.
• Read a line from right to left. The right side follows arrows to a value, and the left side moves an arrow.
• Insertion needs the link copied before it is changed. Reversal needs nxt saved before cur.next is changed.
• A box that no name or attribute can reach is a candidate for garbage collection. A box stays in memory while any arrow reaches it.
• Draw first, then run the code. If the output differs from the drawing, check the arrow you drew for the line that surprised you.