Remove every occurrence of a value

Why it matters

Removing a value from a list is one of the most common list tasks. A list of user IDs might need every copy of a banned ID removed. A list of tasks might need every finished task taken out. The task sounds simple, but the code has three places where it can go wrong: the first node, a run of equal nodes in a row, and a node that is freed before the walk is finished with it.

The usual wrong answer is to remove one match and stop. The usual second wrong answer is to remove matches while walking, but to move the walk forward in a way that skips the node after a removed one. Both bugs produce a list that looks almost right, and both are easy to miss when testing with only one match.

This lesson shows one walk that handles all of these cases. It uses the singly linked list from the earlier lessons of this module. A node has a value and a next pointer, and nothing else. The walk keeps two pointers as local variables, and it is built so that every node is looked at once. Doubly linked lists and their sentinel nodes are covered in the lessons before this one.

The idea: keep the last node you kept

Removing a node from a singly linked list needs one thing that the node itself does not have. To take out a node, you must change the next pointer of the node before it. A singly linked list only stores next, so you cannot ask a node for the one before it. The walk has to remember that node.

The walk uses two pointers:

• cur is the node being looked at now.
• prev is the last node that was kept. It is nullptr when no node has been kept yet.

Each step of the walk does one of two things. If cur does not match, cur is kept, so prev moves to cur. If cur matches, it is removed. In that case prev does not move, because the node that was removed was not kept. The walk then moves cur forward.

There is one more rule. The next pointer of cur must be read before cur is removed, because after delete cur the node no longer exists. So the code saves next first, works with cur, and then moves cur to the saved next.

Here is the core loop as a fragment. It is not runnable on its own. The full program comes later.

Node* prev = nullptr;
Node* cur = head;
while (cur != nullptr) {
    Node* next = cur->next;     // save first, because cur may be deleted
    if (cur->value == target) {
        if (prev == nullptr) {
            head = next;        // the first node is gone, so head moves
        } else {
            prev->next = next;  // skip over cur
        }
        delete cur;
    } else {
        prev = cur;             // cur is kept
    }
    cur = next;
}

Notice that prev is a local variable here. In a doubly linked list, prev is a field stored inside each node. In this lesson it is only a variable in the function, and it points at the last kept node.

Example 1: a match in the middle

Start with the list 1, 2, 3 and remove the value 2. The list has three nodes. Call them N1, N2 and N3. The head points at N1.

The loop ends when cur is nullptr. The walk looked at three nodes and removed one. The result is 1, 3.

Step 2 shows the key rule. The node after the removed node is saved before N2 is deleted. The line prev->next = next then links N1 to N3. The node N1 stays as the last kept node, so the walk can carry on from it.

Example 2: a match at the head, and a run of matches

This example is harder. Start with 2, 2, 1, 2, 2, 3 and remove every 2. The list starts with a match, and there is a run of two 2s in the middle and another run at the end. Call the nodes A (2), B (2), C (1), D (2), E (2) and F (3).

Steps 1 and 2 show the head case. When prev is nullptr, there is no node before the removed one. The only pointer that can point at the removed node is head, so head moves forward. A list with two matches at the start needs two head moves.

Steps 4 and 5 show a run. The node C is kept, so prev is C. Both D and E are removed while prev stays at C. If prev had moved to D after removing it, step 5 would write into a node that no longer exists. That is the second common bug in the mistakes section.

The walk removed four nodes and kept two. It looked at all six nodes, once each.

Example 3: every node matches, and an empty list

The last two cases test the edges. First, every node matches, as in 4, 4, 4 with target 4. Each step is a head case. head moves forward each time, and prev stays nullptr. After three steps, cur and head are both nullptr. The list is empty, and removed is 3.

Second, an empty list is head == nullptr. The loop body never runs, so the function does nothing and returns zero. The while (cur != nullptr) test is the only check the code needs. There is no special case for an empty list.

If no node matches, as in 1, 3, 5 with target 2, every node is kept. prev moves along the list, head never changes, and the list comes out the same as it went in.

Why not restart from the head each time?

A simpler idea is to search for the first match, remove it, and then start the search again from the head. Repeat until no match is found. This works, but it does far more work than the walk.

Take a list of 1,000 nodes. The first 500 hold the value 1, and the last 500 hold the value 2. To remove every 2, the restart method first walks past 500 ones to reach the first 2. It removes that node, then walks from the head past the 500 ones again to reach the next 2. That repeats 500 times. Each search walks about 500 nodes, so the total is about 250,000 steps. The walk in this lesson looks at each of the 1,000 nodes once, and does the same removals with no searching again.

The restart method is slower because it throws away what it already knows. After it passes the 500 ones, the next search should start from the place where the last one was, not from the head. The prev pointer in the walk is exactly that memory. It keeps the walk's place, so nothing is searched twice.

The full program

The program below builds lists from vectors, runs the function on the five cases above, prints each list, and frees the memory. It counts the number of nodes the loop visited, so you can see that each node is visited once.

The program prints this output. It was built with g++ -std=c++20 -Wall -Wextra -g -fsanitize=address,undefined and ran with no sanitizer report.

== middle match (remove 2)
before: [1 2 3]
after:  [1 3]
removed 1, visited 3 of 3 nodes
== head run and a later run (remove 2)
before: [2 2 1 2 2 3]
after:  [1 3]
removed 4, visited 6 of 6 nodes
== every node matches (remove 4)
before: [4 4 4]
after:  []
removed 3, visited 3 of 3 nodes
== no match (remove 2)
before: [1 3 5]
after:  [1 3 5]
removed 0, visited 3 of 3 nodes
== empty list (remove 2)
before: []
after:  []
removed 0, visited 0 of 0 nodes

Why each node is visited once

Each pass of the loop does exactly one of two things with cur. It either keeps the node, or it removes the node. In both cases cur then moves to next, the node that followed cur before anything changed. The loop never moves cur back, and it never moves cur to a node that was already visited.

There is one subtle point. After a node is removed, the code does not read its next again, because next was saved first. The pointer prev never points at a removed node, because it only moves to nodes that are kept. So the walk never reads freed memory and never revisits a node.

The counter visited shows this. For a list of n nodes, the loop body runs n times. In the runs above, visited equals the size of the list every time. A walk that revisited a node would show a count bigger than the size, and a walk that skipped a node would show a count smaller than the size.

The walk changes the list in place. It uses no extra memory that grows with the list, only the two pointers and the saved next. Its running time grows in line with the length of the list.

Common mistakes and the messages you will see

The three mistakes below all compile without any warning under -Wall. The messages come from running the buggy versions with g++ -std=c++20 -Wall -Wextra -g -fsanitize=address. Memory addresses in the messages will differ on your machine.

Mistake 1: reading cur->next after the delete

A common version of the loop reads cur->next at the bottom, after the removal:

if (cur->value == target) {
    // ... unlink cur ...
    delete cur;
} else {
    prev = cur;
}
cur = cur->next;   // cur was just deleted

When the removed node is the one in the middle, this reads memory that was freed. The sanitizer reports it like this:

ERROR: AddressSanitizer: heap-use-after-free
READ of size 8 at 0x7262cc5e0058 thread T0
    #0 in removeAll(Node*&, int) bug_reads_freed.cpp:63
freed by thread T0 here:
    #1 in removeAll(Node*&, int) bug_reads_freed.cpp:58

The message names the line that reads the freed node and the line that freed it. The fix is the rule from the core loop: save next before the removal, then move cur to the saved value.

Mistake 2: moving prev after a removal

This version moves prev at the bottom of the loop for every node, including the removed ones:

Node* next = cur->next;
if (cur->value == target) {
    if (prev == nullptr) head = next; else prev->next = next;
    delete cur;
}
prev = cur;        // wrong: cur may have just been deleted
cur = next;

On the list 2, 2, 1, 2, 2, 3 with target 2, the first node is removed, and prev becomes that freed node. The second node is then a match too, and the line prev->next = next writes into freed memory. The sanitizer stops the program at that write:

ERROR: AddressSanitizer: heap-use-after-free
WRITE of size 8
    #0 in removeAll(Node*&, int) bug_prev_moves.cpp:54

Line 54 in that file is prev->next = next;, which is the write. Move prev only in the branch where the node is kept.

Mistake 3: passing the head by value

The function must change the caller's head when the first node is removed. If the parameter is Node* head, the function changes only its own copy:

RemoveResult removeAll(Node* head, int target) {   // wrong: a copy of the pointer

The caller's head still points at the first node, which has been deleted. The next time the caller uses the list, it reads freed memory:

ERROR: AddressSanitizer: heap-use-after-free
READ of size 4
    #0 in printList(char const*, Node const*) bug_by_value.cpp:28
    #1 in runCase(char const*, std::vector<int, std::allocator<int> >, int) bug_by_value.cpp:75

The fix is the & in Node*& head, which passes the caller's pointer itself.

The standard library

The standard library has ready-made functions for this task. std::forward_list has std::erase(list, value) from C++20, and it returns the number of elements removed. std::list has a member function remove(value). Use them in real code. Write the walk yourself when the list has an extra rule, such as keeping the removed nodes for later.

Built with g++ -std=c++20 -Wall -Wextra, std::erase(fl, 2) on the list 2, 2, 1, 2, 2, 3 returns 4 and leaves 1, 3. l.remove(2) on a std::list leaves 1, 3.

Practice

Exercise 1: trace by hand

Trace removeAll on the list 7, 7, 8, 7 with target 7. Write cur, prev and the list after each step, and give the final removed and visited counts.

Show the answer

Step 1: cur is the first 7, prev is nullptr. It matches, so head moves to the second node. The list is 7, 8, 7 and removed is 1.

Step 2: cur is the second 7, prev is nullptr. It matches, so head moves to 8. The list is 8, 7 and removed is 2.

Step 3: cur is 8, prev is nullptr. It does not match, so prev becomes the node 8. The list is 8, 7.

Step 4: cur is the last 7, prev is the node 8. It matches, so prev->next becomes nullptr. The list is 8, and removed is 3.

The final list is 8. The counts are removed 3 and visited 4.

Exercise 2: remove the even values

Write void removeEven(Node*& head) that removes every node whose value is even. Use the same loop, with a different test.

Show the answer

void removeEven(Node*& head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;
        if (cur->value % 2 == 0) {
            if (prev == nullptr) {
                head = next;
            } else {
                prev->next = next;
            }
            delete cur;
        } else {
            prev = cur;
        }
        cur = next;
    }
}

The only change from removeAll is the test in the if. Run on the list 2, 3, 4, 6, 7, 8, 1, it leaves 3, 7, 1. Run on the list 4, 6, it leaves an empty list.

Exercise 3: why prev does not move on a match

In one sentence each, explain what goes wrong if prev moves to cur even when cur matches and is removed, for the list 1, 2, 2, 3 with target 2.

Show the answer

After the first 2 is removed, prev points at a freed node. The second 2 is then a match, and the line prev->next = next writes into freed memory. Sanitizers report that write as a heap-use-after-free error. Without a sanitizer, the write may appear to work, and the bug shows up later, when the list is read.

Exercise 4: count the visits

For a list with n nodes, how many times does the loop body run in removeAll, no matter how many nodes match? Explain why in two sentences.

Show the answer

The loop body runs exactly n times. Each pass moves cur to the saved next, and that node is the next node in the original list. Every node is cur on exactly one pass, and no pass moves cur back.

Exercise 5: a removal that keeps the first node

Write void removeAfterFirst(Node* head, int target) that removes every node with the value target, but never removes the node head points at, even if it matches. Use prev as the last kept node, and start prev at head.

Show the answer

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

The first node is kept by starting prev at head instead of nullptr, so the head case never runs. The list 2, 2, 1, 2 with target 2 becomes 2, 1. This version does not change the caller's head, because the head node is never removed, so the parameter can be a plain pointer.

Summary

• Keep two pointers while walking: cur is the node being checked, and prev is the last node kept.
• Save cur->next before any removal, because a deleted node can no longer be read.
• Move prev only when a node is kept, so a run of matches is removed from the same kept node.
• When prev is nullptr, the removed node is the first node, so the head pointer moves forward.
• Pass the head by reference, so the caller sees the change when the first node is removed.