ars.me My personal website

(FAQ) Removing elements while iterating over a collection

Q: Why does removing elements from a list while iterating over it “skip” some elements?

A:

Many programming newcomers try to do something like the following:

# pseudocode
for index in list.indices {
    if (some_condition) {
        list.remove(index);
    }
}

and are surprised to find that some elements that should be removed are not.

To understand why this happens, imagine that we want to remove all bs from the list [a, b, b, c] while looping over it as in the pseudocode above. It’ll look something like this:

+-----------------------+
|  a  |  b  |  b  |  c  |
+-----------------------+
   ^ (first iteration)
   
+-----------------------+
|  a  |  b  |  b  |  c  |
+-----------------------+
         ^ (next iteration: we found a 'b' -- remove it)
         
+-----------------------+
|  a  |     |  b  |  c  |
+-----------------------+
         ^ (removed b)
         
+-----------------+
|  a  |  b  |  c  |
+-----------------+
         ^ (shift subsequent elements down to fill vacancy)
         
+-----------------+
|  a  |  b  |  c  |
+-----------------+
               ^ (next iteration)

Notice that we skipped the second b! Once we removed the first b, elements were shifted down and our for-loop consequently failed to touch every element of the list.

This problem can be solved if we iterate over the list backwards:

+-----------------------+
|  a  |  b  |  b  |  c  |
+-----------------------+
                     ^ (first iteration)
   
+-----------------------+
|  a  |  b  |  b  |  c  |
+-----------------------+
               ^ (next iteration: we found a 'b' -- remove it)
         
+-----------------------+
|  a  |  b  |     |  c  |
+-----------------------+
               ^ (removed b)
         
+-----------------+
|  a  |  b  |  c  |
+-----------------+
               ^ (shift subsequent elements down to fill vacancy)
         
+-----------------+
|  a  |  b  |  c  |
+-----------------+
         ^ (next iteration)
         
etc.

Since removing an element results in subsequent elements being shifted down as opposed to previous elements being shifted up, iterating in reverse order circumvents the skipping issue.

However, there are generally better approaches than iterating backwards. For example, in Java, the appropriate method would be to use an Iterator as returned by the iterator method of Collection and to call remove on it:

Iterator<Object> iter = list.iterator();

while (iter.hasNext()) {
    Object elem = iter.next();
    ...
    if (some_condition)
        iter.remove();
}

In Python, the appropriate method would be to use a list comprehension:

list[:] = [elem for elem in list if not some_condition]

or, possibly, the built-in function filter().