Remove every occurrence of a value in Python

Why this matters

Deleting items from a list is one of the most common jobs in real programs. A shopping cart removes every item with a given product code. A log cleaner removes every line that matches a pattern. A game removes every enemy whose health has reached zero. In each case, the code must visit the whole list, find each match, and take it out without breaking the chain of links that is left behind.

Python's built-in list can do this in one line, such as [x for x in items if x != 2]. That line builds a new list and does not show the links at all. This lesson builds the chain by hand, out of small objects that point at each other, so you can see every link that changes.

This lesson covers a singly linked list, where each node has one link, to the next node. The doubly linked case, with a link backwards as well, is covered in the lesson on sentinel nodes earlier in this module, so it is not repeated here. The job is simple to state, but the code has three traps: a match at the very first node, a run of several matches in a row, and a helper variable that moves when it should not.

The job in plain words

A singly linked list is a chain of boxes. Each box holds a value and an arrow to the next box. The last box has no arrow. Python writes "no next box" as None.

In Python, a box is an object. A class is the recipe for a kind of object. The class below makes a box with a value and a next link.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

__init__ runs when you make a new box. self is the box being made. next_node=None means the second argument is optional, and when it is left out the new box has no next box.

To delete a box from the middle of the chain, you must change the arrow of the box before it. That box should point past the deleted box to the one after it. The deleted box is then left out of the chain. Python frees a box once nothing points at it, so the code does not need a delete call.

So the job has two parts. Find the boxes that match. For each match, change the arrow of the box before it. The first part is a loop. The second part needs a helper variable that always points at the box before the one you are looking at. That helper is the key idea of this lesson.

The walk with a previous pointer

Two variables move through the list together. In Python, each variable is a name that refers to an object. This is called a reference. Assigning a new value to a name moves the reference. It does not change the object.

• cur is the box you are looking at now.
• prev is the last box you kept. It is the box whose arrow must change if cur is removed.

The loop works like this. If cur holds the target, change prev.next to skip cur. Then prev stays where it is, because it is still the last kept box. If cur does not hold the target, move prev forward to cur. In both cases, move cur forward to the next box.

Here is the example that the rest of the lesson uses: the list 1 -> 2 -> 2 -> 3, removing every 2. A helper node called dummy sits in front of the list. Its only job is to be prev for the first box. The reason for the dummy is explained in the next section.

def remove_all(head, target):
    dummy = Node(0, head)
    prev = dummy
    cur = head
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next
        else:
            prev = cur
        cur = cur.next
    return dummy.next

Python compares with is when it asks whether a reference is None, because None is a single object. The line while cur is not None reads as "while cur still points at a box".

The trace below shows the loop one step at a time. The marker (prev) shows the box prev points at. The marker (cur) shows the box the loop will look at next. Before the loop starts, prev is the dummy box, which is not printed, so the first line shows only cur.

start: 1(cur) -> 2 -> 2 -> 3
step 1 keep 1: 1(prev) -> 2(cur) -> 2 -> 3
step 2 remove 2: 1(prev) -> 2(cur) -> 3
step 3 remove 2: 1(prev) -> 3(cur)
step 4 keep 3: 1 -> 3(prev)
result: 1 -> 3

Walk through step 2. The loop is looking at the first 2. The code runs prev.next = cur.next, so box 1 now points at the second 2, skipping the first 2. The second 2 is printed with (cur) because it is now the next box to look at. prev did not move, so it is still box 1.

Walk through step 4. The loop is looking at 3, which is not the target. prev moves forward to 3, and cur becomes None, so the loop stops. The result is 1 -> 3.

Matches at the head

The first box can be a match. Then there is no box before it, so there is no prev to change. In the code above, the dummy box solves this. The dummy sits before the head, so it is always the prev for the first real box. When the first real box is removed, the code changes dummy.next, and the function returns dummy.next at the end.

Without a dummy, the first box needs its own code. The version below skips matching boxes at the start, then runs the normal loop. It works, but it has two loops where the dummy version has one.

def remove_all_no_dummy(head, target):
    while head is not None and head.value == target:
        head = head.next
    prev = None
    cur = head
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next
        else:
            prev = cur
        cur = cur.next
    return head

The first loop moves head past every matching box at the front. After it finishes, head is either None or a box that does not match. Only then does the second loop start, and by then prev is never None when a match is found, because the first box is kept.

Both versions give the same result. The dummy version is easier to keep correct, because the head is not a special case.

Runs of matches

A run is several matches in a row. The list 2 -> 2 -> 2 -> 3 has a run of three 2s at the head. The list 1 -> 2 -> 2 -> 3 -> 2 -> 4 -> 2 has a run in the middle and a single match at the end.

The loop handles runs without any extra code. Each match in a run causes one unlink, and prev stays put. The next box is then checked, and it is another match, so it is also unlinked. The loop does not need to know that the box is part of a run.

The helper functions build and to_list make a list from numbers and read one back into a Python list. They are used by every example from here on.

def build(*values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head
 
 
def to_list(head):
    out = []
    cur = head
    while cur is not None:
        out.append(cur.value)
        cur = cur.next
    return out

The *values in build gathers any number of arguments into one tuple, which is a read-only sequence. Calling build(2, 2, 2, 3) gives values the value (2, 2, 2, 3). The reverse loop builds the chain from the last value back to the first, so each new box can point at the box already built.

The program below runs the function on five lists. The first has a run at the head, the second has runs in the middle and at the end, the third is all matches, the fourth has no matches, and the fifth is empty.

a = remove_all(build(2, 2, 2, 3), 2)
print("runs at head:", to_list(a))
 
b = remove_all(build(1, 2, 2, 3, 2, 4, 2), 2)
print("runs in middle:", to_list(b))
 
c = remove_all(build(5, 5, 5), 5)
print("all match:", to_list(c))
 
d = remove_all(build(1, 2, 3), 9)
print("no match:", to_list(d))
 
e = remove_all(None, 4)
print("empty input:", to_list(e))

The output from one run of the five calls above was this.

runs at head: [3]
runs in middle: [1, 3, 4]
all match: []
no match: [1, 2, 3]
empty input: []

The last case is the empty list. The loop never runs, and dummy.next is None, so the function returns None. This is the correct answer for an empty list. to_list(None) returns an empty Python list, which is why the last line prints [].

Why the loop is correct

A loop is correct when something stays true on every pass. For this loop, the thing that stays true is this: the boxes from the dummy up to prev form a list that holds no target value, and every box after prev is still untouched.

At the start, prev is the dummy and the list before it is empty, so the statement is true. Each pass either removes cur, which leaves the kept part unchanged, or moves prev onto cur, which adds a box that is not a target to the kept part. Either way the statement stays true. When cur becomes None, every box has been looked at, so the kept part holds every box that is not a target.

This is a useful way to check your own list code. Write down what is true before the loop and after each step, and check that the statement still holds.

Each node is visited once

A good list function visits each box a fixed number of times. This function visits each box exactly once. cur moves forward through the list one step at a time, and it never moves back. prev only moves forward too, and it never moves past cur. When a box is removed, the loop does not visit it again, because cur already moved to the box after it.

To check this, add a counter that goes up each time the loop body runs. Put visits += 1 at the top of the loop in remove_all and in remove_all_no_dummy, and return the count with the result. Then run both on the eight-box list 1 -> 2 -> 2 -> 3 -> 2 -> 4 -> 5 -> 6. The output from one run was this.

visits with dummy: 8 for 8 nodes
visits without dummy: 8 for 8 nodes

Both counts equal the number of boxes. The loop body runs once per box, so the time the function takes grows in a straight line with the length of the list. Programmers describe this as O(n) time, where n is the number of boxes. The function also needs only three variables however long the list is. That is O(1) extra space. The time and space complexity lesson in this course explains these terms in more detail.

A check against a known-good answer is a good way to gain confidence. The program below makes 2000 random lists of up to 11 numbers, each number from 0 to 3. It compares the result of both functions with a list comprehension, which is Python's short way to build a new list by filtering. The comprehension [x for x in values if x != 2] keeps every value that is not 2.

import random
 
rng = random.Random(42)
checked = 0
for t in range(2000):
    n = rng.randrange(12)
    values = [rng.randrange(4) for _ in range(n)]
    expected = [x for x in values if x != 2]
    got = to_list(remove_all(build(*values), 2))
    got2 = to_list(remove_all_no_dummy(build(*values), 2))
    if got != expected or got2 != expected:
        raise AssertionError(f"mismatch on {values}")
    checked += 1
print("random cases matching list comprehension:", checked)

The output from one run was random cases matching list comprehension: 2000. The random seed 42 makes random.Random produce the same numbers every time, so the result can be repeated.

Common mistakes

Moving prev on a match. This is the most common bug. The code keeps prev = cur after the if block, so prev moves even when cur is removed. The next match then changes the wrong box's arrow, and the match is left in the list. Here is the wrong version and its output from one run.

def remove_all_wrong(head, target):
    dummy = Node(0, head)
    prev = dummy
    cur = head
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next
        prev = cur
        cur = cur.next
    return dummy.next
 
 
print(to_list(remove_all_wrong(build(2, 2, 3), 2)))

[2, 3]

The output [2, 3] still contains a 2. The second 2 was never removed, because prev had moved onto the first 2, which was about to be removed. The fix is to move prev only in the else branch.

Forgetting the head case. Remove the first loop from remove_all_no_dummy and you get a head-only version. It fails when the first box matches, because prev is still None.

def remove_head_only(head, target):
    prev = None
    cur = head
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next
        else:
            prev = cur
        cur = cur.next
    return head
 
 
remove_head_only(build(2, 3), 2)

The last line of the error from one run was this. Python prints a longer traceback above it, and the line that failed was prev.next = cur.next.

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

The message says that prev is None, which cannot store a new attribute, so .next cannot be set on it. The dummy node, or the first loop in remove_all_no_dummy, prevents this.

Forgetting to move cur. If the loop does not run cur = cur.next on every pass, the loop looks at the same box forever. The advance must be at the bottom of the loop body, outside the if, so both branches reach it.

Clearing the removed box's arrow. The unlink prev.next = cur.next leaves cur.next pointing at the box after the removed one. The loop depends on that link to reach the rest of the list. Setting cur.next = None as part of the removal would end the walk early and lose every box after the match.

Practice

Exercise 1. Trace remove_all on the list 4 -> 4 -> 1, removing 4. What is the result?

Show the answer

The result is the list 1, which to_list prints as [1]. The first two boxes match, and the first is at the head, so dummy.next changes twice. The third box does not match, so prev moves to it, and the list is left with one box holding 1.

Exercise 2. Why does prev stay in place after a match, instead of moving forward to cur?

Show the answer

After a match, cur is taken out of the chain. The box prev points at must now point at the box after cur. If prev moved to cur, the next change would happen on the removed box, and the box that should have been changed would stay in the list. Keeping prev on the last kept box means the next change lands on the right box.

Exercise 3. Write remove_all_counting. It removes every occurrence of target and returns how many boxes it removed.

Assigning a new value to a parameter inside a function does not change the caller's variable, because the parameter is only a local name. The easy fix in Python is to return two values. A function can return a tuple, which is a pair in this case.

Show the answer

def remove_all_counting(head, target):
    dummy = Node(0, head)
    prev = dummy
    cur = head
    removed = 0
    while cur is not None:
        if cur.value == target:
            prev.next = cur.next
            removed += 1
        else:
            prev = cur
        cur = cur.next
    return dummy.next, removed
 
 
result, removed = remove_all_counting(build(4, 4, 1), 4)
print("removed", removed, "left", to_list(result))

The output from one run was removed 2 left [1].

Exercise 4. Write remove_negatives(head) that removes every box whose value is less than zero, and returns the new head. Test it on -1 -> 2 -> -3 and on -5 -> -6.

Show the answer

def remove_negatives(head):
    dummy = Node(0, head)
    prev = dummy
    cur = head
    while cur is not None:
        if cur.value < 0:
            prev.next = cur.next
        else:
            prev = cur
        cur = cur.next
    return dummy.next
 
 
print(to_list(remove_negatives(build(-1, 2, -3))))
print(to_list(remove_negatives(build(-5, -6))))

The output from one run was [2] and then []. The second input returns an empty list, because every box is removed and dummy.next is None.

Exercise 5. The head-only version from the mistakes section fails only on some inputs. Describe the smallest input that causes the AttributeError.

Show the answer

A list whose first box holds the target value. For example, the one-box list 2 with target 2. The first pass sees the match, but prev is still None, so prev.next = cur.next fails. A list whose first box does not match, such as 3 -> 2, runs without error, because prev is set to the first box before any match is found. The output from one run was [3].

Summary

• Walk the list with two variables: cur for the box being checked, and prev for the last box kept.
• On a match, change prev.next to skip cur, and leave prev where it is.
• Put a dummy node in front of the head so the first box is never a special case.
• A run of matches needs no extra code, because each match is unlinked in turn while prev stays put.
• Each node is visited once, so the function takes time proportional to the length of the list.
• Moving prev on a match is the most common bug, and it leaves matches in the list.