Debugging lab: pointer bugs in lists

Why this matters

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. Most bugs in list code are pointer bugs. A pointer bug often does not crash on the line that caused it. The damage happens on one line, and the crash shows up a few lines later, or only for one input.

The earlier lessons in this module built the list operations one at a time: insert, delete, reverse, merge and the sentinel version for doubly linked lists. This lab works the other way round. It gives you seven functions that look like the ones from those lessons. Each one has one bug. For each bug you read the code, predict what it does, dry-run it on paper, run it, and then fix it.

A dry run means following the code one line at a time on paper. After each line you write down the value of every variable. Programmers do this when they cannot run the code, or when they want to understand a bug before they touch the keyboard. You will do it for all seven bugs.

The lab uses no new syntax. The skill it builds is reading pointer code slowly and noticing the line where a pointer already points at the wrong thing.

Tools for this lab

The examples were run with g++ 15.2.0 on Linux. Any compiler that supports C++20 will work. The two compiler options used here are these.

• -std=c++20 selects the 2020 version of the C++ language.
• -Wall turns on the common warnings. Read every warning. Bug 7 is reported as a warning before you run anything.

The lab also uses AddressSanitizer. A sanitizer is a checker that the compiler adds to your program. AddressSanitizer watches every memory read and write while the program runs. It stops at the first bad one and prints where it happened. Build a second copy of the program with it, and run that copy when a plain run fails without a clear message.

g++ -std=c++20 -Wall -g -o buggy buggy.cpp
g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o buggy_asan buggy.cpp
./buggy_asan 1

The -g option keeps line numbers in the output, so the error messages point at your source lines. The undefined part of the sanitizer also reports some undefined behaviour, which is code the C++ standard leaves unspecified.

Every bug has its own test. The test is one short block in main, and each bug section below shows that test. Run the buggy program with the number of the test, for example ./buggy 3. The line numbers in the sanitizer output below depend on how you lay out buggy.cpp, so yours may differ.

The shared helpers

Every function in this lab works on the same node type. Here is the type and three small helpers.

struct Node {
    int value;
    Node* next = nullptr;
};

Node* next is a pointer. A pointer stores an address, which is the place in memory where something lives. So next stores the address of the node after this one. The = nullptr part means a new node starts with no next node. nullptr is C++'s word for "a pointer that points at nothing".

The next helper builds a list from a list of numbers.

Node* build(std::initializer_list<int> values) {
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int v : values) {
        Node* n = new Node{v};
        if (tail == nullptr) head = n; else tail->next = n;
        tail = n;
    }
    return head;
}

new Node{v} asks the system for memory for one node, fills in value with v, and returns the address of that node. Memory from new lives in an area called the heap. It stays there until your program calls delete on it. The variable head holds the address of the first node, and tail holds the address of the last node so far.

The -> arrow reads a field through a pointer. cur->value means "the value of the node that cur points at". cur->next means "the next pointer of the node that cur points at".

The third helper prints the list. It starts at head and moves forward until it reaches nullptr.

void print(const char* label, const Node* head) {
    std::cout << label << ": ";
    if (head == nullptr) std::cout << "(empty)";
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        std::cout << cur->value;
        if (cur->next != nullptr) std::cout << " -> ";
    }
    std::cout << '\n';
}

The loop variable cur is a pointer that visits one node at a time. The const in const Node* means this function will not change the nodes. The arrows in the output are plain text, and the if avoids a trailing arrow after the last value.

The last helper gives memory back.

void free_list(Node* head) {
    while (head != nullptr) {
        Node* next = head->next;
        delete head;
        head = next;
    }
}

The order inside the loop matters. The line Node* next = head->next; saves the address of the next node before delete head gives the current node's memory back. Keep that order in mind. Bug 4 in this lab breaks the same rule.

Bug 1: append crashes on an empty list

The first function adds a value to the end of a list. It walks to the last node and attaches a new node there.

void append(Node* head, int value) {
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = new Node{value};
}

The idea is right for a list with at least one node. Start at the first node, keep moving while the next pointer is not nullptr, and then attach the new node to the last node. The bug appears when the list is empty.

Dry-run the test below. It appends a value to an empty list.

Node* empty = nullptr;
append(empty, 4);

call: append(empty, 4), where empty is nullptr
  cur = head              cur is nullptr
  cur->next               there is no node, so there is nothing to read

The while test reads cur->next. When cur is nullptr, there is no node to read from. Reading through a nullptr is called a null dereference. Following a pointer means reading the memory it points at. A null pointer points at no memory, so the read fails.

Run the plain build. Nothing is printed, and the shell reports exit code 139. Exit code 139 means the program was stopped by a segmentation fault. A segmentation fault is the operating system stopping a program that touched memory it is not allowed to use.

The sanitizer build explains the same failure.

==178090==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc ...)
==178090==The signal is caused by a READ memory access.
    #0 ... in append(Node*, int) ...buggy.cpp:43
    #1 ... in main ...buggy.cpp:118

The address 0x8 is a clue. Inside a node, next sits 8 bytes from the start, because value takes 4 bytes and the compiler adds 4 bytes of padding (unused space) so the pointer starts at a multiple of 8. So reading next from a nullptr tries to read address 0 plus 8. The process ID and the exact pc value change on each run, so this output has been shortened with ....

The fix needs two changes. The first change is an empty-list check. The second change is the & in the parameter. Without the &, a function that sets head changes only its own copy, and the caller's list stays empty. Bug 3 explains this in more detail.

void append(Node*& head, int value) {
    Node* fresh = new Node{value};
    if (head == nullptr) {
        head = fresh;
        return;
    }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = fresh;
}

The test is now two calls and one print.

Node* list = nullptr;
append(list, 4);
append(list, 6);
print("append to empty", list);

append to empty: 4 -> 6

Bug 2: count stops one node early

The second function counts the nodes in a list. It has an empty-list check at the top, so the only problem is in the loop.

int count_nodes(const Node* head) {
    if (head == nullptr) return 0;
    int count = 0;
    for (const Node* cur = head; cur->next != nullptr; cur = cur->next) ++count;
    return count;
}

The loop test is cur->next != nullptr. That test asks whether the node after cur exists. It does not ask whether cur exists. So the loop stops when it reaches the last node, and the last node is never counted.

Dry-run the test on the list 5 -> 6 -> 7.

start    cur = node 5, count = 0
check    cur->next is node 6, not nullptr: enter loop, count = 1, cur = node 6
check    cur->next is node 7, not nullptr: enter loop, count = 2, cur = node 7
check    cur->next is nullptr: loop stops, return 2

Three nodes went in, and the function returns 2. Run it to confirm.

Node* h = build({5, 6, 7});
std::cout << "count: " << count_nodes(h) << '\n';

count: 2

A loop that checks cur->next looks one node ahead. The fix is to check the node you are on, which is cur itself. A loop that moves a pointer forward should test that pointer. When the pointer is nullptr, you have passed the end of the list.

int count_nodes(const Node* head) {
    int count = 0;
    for (const Node* cur = head; cur != nullptr; cur = cur->next) ++count;
    return count;
}

With this version the empty list gives 0 without a special case. The loop never starts, because cur is already nullptr.

Bug 3: remove_first changes only its own copy of head

The third function removes the first node that holds a target value. It works on the list through a head parameter.

void remove_first(Node* head, int target) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr && cur->value != target) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == nullptr) return;
    if (prev == nullptr) head = cur->next;
    else prev->next = cur->next;
    delete cur;
}

The search loop and the middle-node case are right. The bug is in the first-node case. When the target is in the first node, prev stays nullptr, and the code sets head = cur->next. The head here is a parameter, and a parameter is a copy. In C++, passing a pointer without & gives the function a copy of the address. Changing head inside the function changes that copy, and the caller's variable still holds the old address.

Dry-run the test below.

Node* h = build({5, 6, 7});
remove_first(h, 5);
print("after remove 5", h);

call: remove_first(h, 5)    h holds the address of node 5
  cur = node 5, value 5 matches, loop stops
  prev is nullptr, so head = cur->next  (only the copy of head moves to node 6)
  delete cur                            (node 5's memory is given back)
back in main: h still holds the address of node 5
print(h)                                reads node 5 after it was given back

Run the sanitizer build. It stops in print, which is the first line that reads the freed node.

==178094==ERROR: AddressSanitizer: heap-use-after-free on address ...
READ of size 4 at ...
    #0 ... in print(char const*, Node const*) ...buggy.cpp:26
    #1 ... in main ...buggy.cpp:127
freed by thread T0 here:
    #0 ... in operator delete(void*, unsigned long) ...
    #1 ... in remove_first(Node*, int) ...buggy.cpp:66
previously allocated by thread T0 here:
    ...

A read of memory after delete is called a use after free. The memory might still hold the old values, or it might hold anything else. A program cannot rely on either. The output of the plain build is not reliable for the same reason, which is why the sanitizer build is the better tool here. The freed by lines show the line that gave the memory back, and the previously allocated by lines show where the node was made.

The fix is to take the head by reference. The Node*& in the parameter means the function works on the caller's own variable, not on a copy.

void remove_first(Node*& head, int target) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr && cur->value != target) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == nullptr) return;
    if (prev == nullptr) head = cur->next;
    else prev->next = cur->next;
    delete cur;
}

Now head = cur->next changes h in main. The test prints after remove 5: 6 -> 7.

Bug 4: remove_below reads a node after deleting it

The fourth function removes every node with a value below a limit. It walks the list with prev and cur, like the function in bug 3, but it deletes inside the loop.

void remove_below(Node*& head, int limit) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        if (cur->value < limit) {
            if (prev == nullptr) head = cur->next;
            else prev->next = cur->next;
            delete cur;
            cur = cur->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

The relinking is right. The bug is the last line of the first branch. After delete cur, the code reads cur->next, and cur now points at memory that was given back. Use this dry-run on the list 1 -> 5 -> 2 -> 8 -> 3 with limit 4.

cur = node 1, value 1 is below 4
  prev is nullptr, so head = node 5
  delete cur                     node 1's memory is given back
  cur = cur->next                reads node 1 after it was given back

Run the sanitizer build with the test.

Node* h = build({1, 5, 2, 8, 3});
remove_below(h, 4);
print("after remove below 4", h);

==178098==ERROR: AddressSanitizer: heap-use-after-free on address ...
READ of size 8 at ...
    #0 ... in remove_below(Node*&, int) ...buggy.cpp:78
freed by thread T0 here:
    #0 ... in operator delete(void*, unsigned long) ...
    #1 ... in remove_below(Node*&, int) ...buggy.cpp:77

The read is on line 78, which is the line after delete cur on line 77. The sanitizer report points at the two lines in order, so you can see the cause.

The fix saves the node to delete in a separate variable. The loop then moves on, the code relinks around the saved node, and only then deletes it. The rule is simple. Read everything you need from a node before you delete it.

void remove_below(Node*& head, int limit) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        if (cur->value < limit) {
            Node* doomed = cur;
            cur = cur->next;
            if (prev == nullptr) head = cur;
            else prev->next = cur;
            delete doomed;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

The name doomed is a plain label for the node that is about to be deleted. After the fix, the test prints after remove below 4: 5 -> 8.

Bug 5: insert_after makes the new node point at itself

The fifth function puts a new node right after node p. The new node should sit between p and the node that used to follow p.

void insert_after(Node* p, int value) {
    Node* fresh = new Node{value};
    p->next = fresh;
    fresh->next = p->next;
}

The two lines at the end are in the wrong order. The first line makes p->next point at fresh. Once that line has run, p->next and fresh are the same node. The last line then sets fresh->next to fresh. The node points at itself.

Dry-run the test on the list 5 -> 6 -> 7, with p set to node 5.

Node* h = build({5, 6, 7});
insert_after(h, 9);

start    p = node 5, p->next = node 6
  fresh = new node 9
  p->next = fresh          p->next is now node 9, so node 6 is not reachable from node 5
  fresh->next = p->next    p->next is fresh, so fresh->next = fresh

The result is wrong in two ways. Node 9 loops back to itself, so any walk down the list never ends. Nodes 6 and 7 can no longer be reached from the list head, so they are lost. The program has no pointer to them, and it cannot give their memory back.

The test below reports the self-loop without walking the list. Walking it would never end.

Node* h = build({5, 6, 7});
insert_after(h, 9);
Node* fresh = h->next;
std::cout << "fresh points to itself: " << std::boolalpha << (fresh->next == fresh) << '\n';

fresh points to itself: true

The fix is to save the rest of the list before p is changed. Two lines swap places, so the order matters.

void insert_after(Node* p, int value) {
    Node* fresh = new Node{value};
    fresh->next = p->next;
    p->next = fresh;
}

Now fresh->next takes the old next node first, and p->next is set last. The test prints 5 -> 9 -> 6 -> 7, which is the list you wanted.

Bug 6: reverse loses the rest of the list

The sixth function reverses a list in place. It walks the list with a pointer prev that holds the node already reversed, and it turns each next pointer around as it goes.

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        cur->next = prev;
        prev = cur;
        cur = cur->next;
    }
    return prev;
}

The bug is in the last line of the loop. The line cur->next = prev overwrites the only pointer that leads from cur to the rest of the list. Then cur = cur->next reads the new value, which is the old prev, nullptr, not the old next node. Dry-run the list 1 -> 2 -> 3.

start    prev = nullptr, cur = node 1 (node 1 points at node 2)
  cur->next = prev       node 1 now points at nullptr; node 2 is no longer reachable from node 1
  prev = cur             prev = node 1
  cur = cur->next        cur = nullptr, not node 2
loop stops, return prev, which is node 1

The test is the following.

Node* h = build({1, 2, 3});
Node* r = reverse(h);
print("reversed", r);

reversed: 1

The output has one value. Nodes 2 and 3 are lost. Run the sanitizer build to see the leak.

==178417==ERROR: LeakSanitizer: detected memory leaks
 
Direct leak of 32 byte(s) in 2 object(s) allocated from:

A leak is memory that is still allocated but can no longer be reached. Nodes 2 and 3 are unreachable, and node 1 leaks too, because this test never frees r. Each node is 16 bytes on this machine, so the three nodes make 48 bytes.

The fix saves the old next pointer in its own variable before anything is overwritten.

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Trace the list 1 -> 2 -> 3 with this version. After the first pass, node 1 points at nullptr. After the second pass, node 2 points at node 1. After the third pass, node 3 points at node 2, and prev is node 3. The output is reversed: 3 -> 2 -> 1.

Bug 7: = assigns instead of comparing

The seventh function reports whether a target value is in the list. It has the right loop and the right return values. The problem is one character.

bool contains(Node* head, int target) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->value = target) return true;
    }
    return false;
}

In C++, = assigns a value and == compares two values. The line cur->value = target writes target into the node. The result of an assignment is the value that was assigned. A nonzero number counts as true in an if, so the test is true whenever target is not 0. The function returns true on the first node, and it has already changed that node.

The compiler sees the problem before the program runs. Build the buggy version with -Wall and read the warning.

buggy.cpp: In function ‘bool contains(Node*, int)’:
buggy.cpp:108:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  108 |         if (cur->value = target) return true;

Dry-run the test below, which searches for 9 in the list 5 -> 6 -> 7.

Node* h = build({5, 6, 7});
std::cout << "contains 9: " << std::boolalpha << contains(h, 9) << '\n';
print("list now", h);

start    cur = node 5
  cur->value = 9        node 5 now holds 9, and the assignment's result 9 is true
  return true

contains 9: true
list now: 9 -> 6 -> 7

The search said yes, and the list was changed in the process. The fix is ==, and the parameter becomes const Node*. The const is a second line of defence. With const, the compiler refuses any line that writes to a node. Bug 7 is the case where that refusal helps most. A reader who sees contains as a read-only search will not write a line that changes a node.

bool contains(const Node* head, int target) {
    for (const Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->value == target) return true;
    }
    return false;
}

With this version, contains(h, 6) returns true, contains(h, 9) returns false, and the list is unchanged.

The complete fixed program

The file below contains all seven fixed functions and one test for each. Every helper from the start of the lab is included, so the file compiles on its own. Save it as fixed.cpp, compile it with g++ -std=c++20 -Wall -o fixed fixed.cpp, and run ./fixed.

The output of this program is the following. The sanitizer build of the same file runs with no error and no leak report.

fix 1, append to empty: 4 -> 6
fix 2, count: 3
fix 3, remove 5: 6 -> 7
fix 4, remove below 4: 5 -> 8
fix 5, insert 9 after 5: 5 -> 9 -> 6 -> 7
fix 6, reverse: 3 -> 2 -> 1
fix 7, contains 6: true
fix 7, contains 9: false
fix 7, list unchanged: 5 -> 6 -> 7

Every free_list call is in main. A leak check passes only when every node is freed, and the free_list calls are what make it pass.

Common mistakes

Each mistake below is one you will make in your own list code. The messages are real g++ output for these mistakes. Line numbers depend on your file.

The first mistake is passing a nullptr literal to a function that takes Node*&. A Node*& must bind to a variable that holds a pointer. A literal nullptr is not a variable, so g++ refuses the call.

errs.cpp:10:12: error: cannot bind non-const lvalue reference of type ‘Node*&’ to a value of type ‘std::nullptr_t’
    10 |     append(nullptr, 4);
note: initializing argument 1 of ‘void append(Node*&, int)’

The fix is to pass a variable: Node* list = nullptr; append(list, 4);.

The second mistake is adding const to a function that writes to a node. The compiler stops the write. This message is what you get when you keep = and add const to the parameter.

errs.cpp:5:24: error: assignment of member ‘Node::value’ in read-only object
    5 |         if (cur->value = target) return true;

Read the message as a clue. The compiler is saying the function writes where it should only read. Usually the fix is ==, not removing the const.

The third mistake is ignoring the -Wparentheses warning. The warning shown in bug 7 is not a style note. It is the compiler telling you that an assignment sits where a test was probably meant.

The fourth mistake is reading the exit code 139 as a bug in the plain build with no further clue. The plain build only says the program crashed. Run the sanitizer build to find the line.

The fifth mistake is deleting a node and then using the variable that held it. Bugs 3 and 4 both do this. In a loop, the safe order is to save what you need, move on, and delete last.

The sixth mistake is forgetting that a pointer copy is not the original. A function that changes head must take Node*&, or return the new head and be called as head = f(head);. The append fix in bug 1 uses the first form.

Practice

Each exercise uses the same helpers as the lab. Write your answer in a file, compile it with -std=c++20 -Wall, and run it with -fsanitize=address,undefined when you can.

Exercise 1: find the bug in pop_front

This function removes the first node and gives its memory back. Dry-run it on the list 4 -> 8, then name the bug.

void pop_front(Node*& head) {
    Node* first = head;
    delete first;
    head = first->next;
}

Show the answer

The bug is a use after free. delete first gives the node's memory back, and then first->next reads that memory. The fix saves the next node first, then deletes the old first node. It also checks for an empty list.

void pop_front(Node*& head) {
    if (head == nullptr) return;
    Node* first = head;
    head = first->next;
    delete first;
}

On the list 4 -> 8, one call leaves 8. A second call leaves the list empty, and a third call does nothing.

Exercise 2: dry-run count_nodes on two small lists

Dry-run the fixed count_nodes on an empty list, then on a list with one node holding 9. Write the value of cur and count at each check.

Show the answer

For the empty list, cur starts as nullptr. The loop test cur != nullptr is false, so the loop never runs, and the function returns 0.

For the one-node list, cur starts at the node holding 9. The test is true, so count becomes 1 and cur becomes nullptr. The next test is false, and the function returns 1.

Exercise 3: write last_value

Write int last_value(const Node* head). It returns the value of the last node, or -1 if the list is empty. Check it on the list 5 -> 6 -> 7 and on an empty list.

Show the answer

int last_value(const Node* head) {
    if (head == nullptr) return -1;
    const Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    return cur->value;
}

The output on the two lists is 7 and -1. The loop tests cur->next, which is correct here, because the function must stop on the last node itself and not one step after it. The empty-list check comes first, so cur->next is never read through nullptr.

Exercise 4: predict the effect of the buggy contains

Use the buggy contains from bug 7, which has = in its test. Predict two things: what it returns for target 0 on the list 5 -> 6 -> 7, and what the list looks like afterwards. Then run it to check.

Show the answer

It returns false. Each node gets the value 0 written into it, and a 0 is false in an if, so the loop goes on to the next node. After the loop ends, the list reads 0 -> 0 -> 0. The function gave the wrong answer for a value that is in the list, and it changed three nodes while doing so.

Exercise 5: write insert_at_front and explain the &

Write void insert_at_front(Node*& head, int value). It puts a new node before the current first node. Then explain what would happen to the list if the parameter had no &.

Show the answer

void insert_at_front(Node*& head, int value) {
    Node* fresh = new Node{value};
    fresh->next = head;
    head = fresh;
}

On the list 1 -> 2, the call with 0 gives 0 -> 1 -> 2. Without the &, head is a copy. The function would link the new node in front of 1, but the caller's variable would still point at node 1. The caller would walk the list from node 1 and never see node 0. Node 0 would be lost, and it would never be freed.

Summary

• A function that changes a list's first node must take Node*& or return the new head.
• Test the node you are on in a loop, and stop when that node is nullptr.
• Read everything you need from a node before you delete it.
• Save the next pointer in its own variable before you overwrite it.
• In C++, = assigns and == compares. A const parameter stops accidental writes.
• Run the AddressSanitizer build when a plain run crashes without a clear message.