Drawing pointer diagrams

Why this matters

Linked structures, such as a list of nodes where each node points at the next, are hard to picture in your head. When you change one pointer, several other pointers may change meaning at once, and it is easy to lose track. A common way to get a linked list wrong is to guess what the pointers point at, guess wrong, and then not find the bug.

A pointer diagram fixes this. You draw a box for every variable and every node, and an arrow for every pointer. Then you change the diagram one line at a time, the same way the code changes. The picture shows you what the code will do before you run it.

This lesson teaches the drawing method, uses it on four changes to a list, and checks each prediction by running the program. It assumes you know what a pointer and a node are. The lesson on dangling and null bugs covers the errors you get when a pointer leads nowhere. Here we assume every pointer in the drawing leads to a real node, except where we say null.

The two marks: boxes and arrows

A pointer is a variable that holds the address of another value. An address is the number that says where a value is stored in memory. A pointer is useful because it can lead you to a value, and it can be copied and changed without moving the value it points at.

A node is a small object that holds a value and a pointer. In the examples in this lesson, a node is a struct with two fields:

struct Node {
    int value;
    Node* next;   // the address of the next node, or nullptr at the end
};

The struct keyword groups two fields into one type. The field next has the type Node*, which means "a pointer to a Node". The comment is part of the meaning, and it is worth writing in your own code.

Draw the picture with two kinds of mark:

1. A box for each variable and each node. A variable box holds a value, or an arrow. A node box holds two slots: the value on the left, and the next pointer on the right.
2. An arrow from a pointer slot to the box it points at. A pointer that holds nullptr gets no arrow. Write the word null in its slot instead, so you can see that it is set on purpose.

A variable name goes beside the box that it names. For example, the variable head is drawn as a small box with an arrow to the first node. The node itself has no name in the code, so we label it with the variable that first points at it, such as a.

Step 1: draw a list

Here is the picture for a list of three nodes. The variable head points at the first node, and each node points at the next.

head
 |
 v
[ 10 | * ]-->[ 20 | * ]-->[ 30 | null ]
   a            b             c

The * stands for a pointer slot with an arrow leaving it. The arrow from the first * goes to the box for node b. The last node holds null, so the list ends there.

The code that builds this picture is:

Node c{30, nullptr};
Node b{20, &c};
Node a{10, &b};
Node* head = &a;

Read each line and draw it. The first line creates node c with value 30 and a null next. The second line creates node b and sets its next to the address of c. The third line creates node a and points it at b. The last line creates the variable head and points it at a. Building the list from the end makes each address available when it is needed.

Worked example 1: walk the list with a finger

Walking a list means following arrows one at a time. Put your finger on the box that head points at, read its value, then move your finger along its arrow. Stop when the arrow is null.

Here is the walk written as code:

#include <iostream>
 
struct Node {
    int value;
    Node* next;
};
 
void print_list(const Node* head) {
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        std::cout << cur->value << " ";
    }
    std::cout << "\n";
}
 
int main() {
    Node c{30, nullptr};
    Node b{20, &c};
    Node a{10, &b};
    Node* head = &a;
 
    print_list(head);
    return 0;
}

The loop variable cur is a second pointer. It starts as a copy of head, which points at a. Each time through the loop, cur = cur->next moves the second pointer along the next arrow. The first time, cur points at a and the loop prints 10. The second time, cur points at b and prints 20. The third time, cur points at c and prints 30. Then cur holds nullptr, the loop stops, and the output is:

10 20 30 

The output has a trailing space after 30, because print_list prints a space after each value. Two things make the walk safe. The loop tests cur != nullptr before it reads cur->value. The loop also moves cur only, and head never moves. After the walk, head still points at a. That is the first rule to remember: a pointer that is only copied and moved does not change the list.

Step 2: predict a change before you draw it

For each change, follow the same three steps:

1. Copy the current picture.
2. Apply the change to the picture by moving only the arrows that the change names.
3. Read the new picture to predict the output, then run the code and compare.

A change to a pointer moves its arrow, and nothing else. A change to a value changes the number inside a box, and no arrow moves. Keep these apart. Many wrong predictions come from moving an arrow that the code did not touch.

Worked example 2: remove the middle node

The code removes the node with value 20. It does this by making a skip over b:

a.next = b.next;

Before the change, the arrow from a goes to b. The statement changes only the arrow from a, and makes it point at whatever b.next points at. That is c.

Draw the picture after the change:

head
 |
 v
[ 10 | * ]------------->[ 30 | null ]
   a                        c
 
[ 20 | * ]-->[ 30 | null ]
   b

Node b still exists. Its box is still there, and its arrow still goes to c. But no arrow from the list reaches b, so it is no longer part of the list. Node b is a local variable, so it stays in memory until main returns.

Here is the full program. Predict the output before you run it.

#include <iostream>
 
struct Node {
    int value;
    Node* next;
};
 
void print_list(const Node* head) {
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        std::cout << cur->value << " ";
    }
    std::cout << "\n";
}
 
int main() {
    Node c{30, nullptr};
    Node b{20, &c};
    Node a{10, &b};
    Node* head = &a;
 
    // Remove the node with value 20: the node before it skips over it.
    a.next = b.next;
 
    print_list(head);
    std::cout << "b still exists, its value is " << b.value << "\n";
    return 0;
}

The picture says the list is 10 then 30, and that b still holds 20. The output agrees:

10 30 
b still exists, its value is 20

Worked example 3: insert at the front

To insert a new node at the front, make the new node point at the old head, then move head to the new node. The order matters. If you move head first, the old head is lost, because the only pointer to it is gone.

Node z{5, head};   // z points at the old head
head = &z;         // head now points at z

Draw the picture before the change, then add the new box z. The first line draws an arrow from z to a, because head at that moment points at a. The second line moves the arrow from head, so head now points at z. The arrow from a is untouched.

before:   head --> a(10) --> b(20) --> c(30) --> null
 
after:    head --> z(5) --> a(10) --> b(20) --> c(30) --> null

The output is:

5 10 20 30 

The list grew by one node, and no existing node was changed. This is the usual pattern for inserting in a linked list: create the new node, point it at the rest of the list, then point the list at it.

Worked example 4: the lost head

A common mistake is to move head forward without saving the first node. The code below does this. The program walks to the last node, then moves head one step forward.

Node* cur = head;
while (cur->next != nullptr) {
    cur = cur->next;
}
std::cout << "last value: " << cur->value << "\n";
 
head = head->next;   // head now skips the first node
print_list(head);

Draw the picture. The walk with cur only moves cur, so the picture is the same as before, with cur ending on c. The statement head = head->next; moves the head arrow from a to b. Node a is still in memory, and its arrow still points at b, but nothing from head can reach it. The list that starts at head is now b then c.

Predict the output, then check it:

last value: 30
20 30 

The loop's cur->next != nullptr test stops when cur is on the last node. The test is safe here because the list is not empty. An empty list is a case where head is nullptr, and the first line of the loop would read through it. The dangling and null lesson covers that case.

Worked example 5: reverse two nodes

This is the hardest change in the lesson. It swaps the first two nodes of a list of four, so that 1 then 2 becomes 2 then 1. The order of the four statements matters, so draw each one and check it.

Node* first = head;        // first points at node 1
Node* second = head->next; // second points at node 2
first->next = second->next; // node 1 now points at node 3
second->next = first;       // node 2 now points at node 1
head = second;              // head points at node 2

Take the statements one at a time. Start with the picture of 1, 2, 3, 4 and the head arrow at 1. Add first and second as two new variable boxes, each with an arrow.

After line 1, first and head both point at node 1, which is the same as the start. After line 2, second points at node 2. After line 3, the arrow from node 1 moves from node 2 to node 3. Node 2 still points at node 3, so for a moment both 1 and 2 point at 3. After line 4, the arrow from node 2 moves from node 3 to node 1. Now 2 points at 1, and 1 still points at 3. After line 5, head points at node 2.

Walking from head now gives 2, then 1, then 3, then 4. The code is:

void print_list(const Node* head) {
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        std::cout << cur->value << " ";
    }
    std::cout << "\n";
}

Running the full program prints:

2 1 3 4 

The order of lines 3 and 4 is the lesson here. If you reverse them, second->next = first; runs first. Then second->next is no longer node 3, so the line first->next = second->next; makes node 1 point at node 1. The list loops and never reaches 4. Drawing each line shows this before you run the code.

Drawing rules that save time

Use these rules for any pointer picture:

• Draw one box for each variable and each node. Name the box by its variable, or by a letter if no variable names it.
• Draw one arrow for each pointer that is not null. Write null in a slot that holds nullptr.
• For each statement, find the one pointer it changes. Move only that arrow. A line that reads a.next = ... changes the arrow in a, and nothing else.
• For a statement that reads a pointer and then writes another, read first and write second. In head = head->next; the right side is read before the left side is written.
• Note every node that no arrow reaches. Mark it as unreachable. Do not delete it in the picture, because it may still be needed to check the change.
• Run the code after you draw. If the output does not match the picture, check the picture first. Most of the time the picture has an arrow you forgot to move.

Common mistakes

1. Moving head before saving the old head. If head = &z; runs first, then z.next = head; makes z point at itself, because head now holds the address of z. The list then loops, and the printing loop never stops. Draw the arrow from the new node first.

2. Moving an arrow that the statement does not name. A line such as first->next = second->next; changes the arrow from first. It does not change the arrow from second. Drawing both arrows before and after each line catches this.

3. Forgetting that a second variable is a second arrow. After Node* q = p;, both p and q have arrows to the same node. Changing p with p = &b; moves only the arrow from p. The arrow from q stays where it was, and q->value still reads the old node.

4. Reading the picture as if it were the memory. A box in a diagram is a node. Its address is a number you do not need to write down. Draw arrows, not addresses, unless the question asks for addresses.

5. Assuming a node with no arrow is gone. A node that no arrow reaches is still in memory. It is only unreachable from that list. A node made with new keeps using memory until it is deleted, which the leaks lesson covers.

6. Drawing the picture after the code instead of during it. A picture made after the change shows the answer you expect, and it hides the step where the bug happened. Draw one line at a time.

Practice

Exercise 1: predict a change to the end of a list

Starting from a list of 1 then 2, what does this change print?

Node c{3, nullptr};
Node b{2, nullptr};
Node a{1, &b};
Node* head = &a;
 
a.next = &c;
print_list(head);

Show the answer

The arrow from a moves from b to c. The arrow from b was nullptr and stays that way, so the list is 1 then 3. The output is:

1 3 

Node b is not in the list any more, but it still exists and still holds 2.

Exercise 2: move the head forward

Starting from the list 10, 20, 30, what does this code print?

Node* head = &a;
head = head->next;
print_list(head);
print_list(&a);

Show the answer

The first move changes only the head arrow, from a to b. The first call prints from b, which gives 20 then 30. The second call starts at a, which still points at b, so it prints all three values. The output is:

20 30 
10 20 30 

The variable a did not move. Only the head variable did.

Exercise 3: insert between two nodes

Starting from the list 10, 20, 30, what does this code print?

Node d{15, a.next};
a.next = &d;
print_list(head);

Show the answer

The new node d is created with its next pointing at b, which is the node that follows a. Then a.next is moved to point at d. The list becomes 10, then 15, then 20, then 30. The output is:

10 15 20 30 

The order is the same as the insert at the front. First point the new node at what comes next, then point the old node at the new one.

Exercise 4: two pointers to one node

What does this program print, and why?

Node b{2, nullptr};
Node a{1, nullptr};
Node* p = &a;
Node* q = p;
 
p = &b;
std::cout << "p points at " << p->value << "\n";
std::cout << "q points at " << q->value << "\n";

Show the answer

After q = p, both pointers hold the address of a. The line p = &b; moves only p, so q still points at a. The output is:

p points at 2
q points at 1

Draw two variable boxes with arrows. Move one arrow, and the other stays where it was.

Exercise 5: predict a loop

A list has three nodes, a with value 1, b with value 2 and c with value 3, linked in that order. Then this line runs:

c.next = &a;

Draw the picture. What happens when print_list(&a) runs, and why?

Show the answer

The arrow from c now points at a, so the list is a loop: a, b, c, then back to a. The loop in print_list only stops when it reaches nullptr, and no node has a null next now. The function prints 1, 2 and 3 over and over, and it does not stop. In a real program you would stop it with a limit on the count, or by making sure the list has no loop. Do not run this one without a limit, because it never finishes.

Summary

• Draw a box for each node and each variable, and an arrow for each pointer that is not null. Write null for nullptr.
• Change the picture one line at a time, moving only the arrow that the line names.
• Insert at the front by pointing the new node at the old head, then moving head. The reverse order loses the list.
• Moving head forward loses the first node, unless another pointer still reaches it.
• Two pointers that copy the same address share one node. Changing one pointer does not change the other.
• Run the code after you draw, and check the picture first when the output does not match.