Python: Removing list element while iterating over list

Question

I'm iterating over a list of elements in Python, do some action on it, and then remove them if they meet certain criteria.

for element in somelist:
    do_action(element)
    if check(element):
        remove_element_from_list

What should I use in place of remove_element? I have seen similar questions asked, but notice the presence of the do_action part that is to be executed for all elements and thus eliminates the solution of using filters.

Can't you split it in two steps i.e. for all elements do the action, then remove elements ? — digEmAll, May 16 '11 at 20:16
You should **NEVER** delete an element from a list while iterating over it in a for loop. You could use a while loop instead. Or, record the indices of all the elements you want to remove and then delete them after the iteration is complete — inspectorG4dget, May 16 '11 at 20:17
For all: I need to modify the list in place, no copies. Actually the list is passed to a function and the list needs to be modified by that function. — Scrontch, May 16 '11 at 20:28
@Scrontch, it's still possible (and better) to loop through the list and then **replace it's contents** as a second pass . That is why I use `[:]` in my answer — John La Rooy, May 16 '11 at 20:39
@inspectorG4dget: Your first sentence is untenable -- see my answer. — John Machin, May 16 '11 at 23:53
@John: @Scrontch wanted to do the deletion in a for loop, which is an inarguably bad idea.. In your example, you used a while loop, which is something that I had suggested in my comment for the exact way in which you are using your while loop. — inspectorG4dget, May 17 '11 at 13:29
@Scrontch: I you haven't accepted an answer yet. I you would, either critique the answers or accept one. It will help those who have posted answers and it will make it more likely for you to get answers in the future. — Steven Rumbalski, May 17 '11 at 15:15

bluepnume · Accepted Answer · 2013-06-16T16:04:00.367

207

You could always iterate over a copy of the list, leaving you free to modify the original:

for item in list(somelist):
  ...
  somelist.remove(item)

edited Jun 16 '13 at 16:04

answered May 16 '11 at 20:15

bluepnume

16,460
8
38
48

2

@Scrontch Given you additional criteria of "modify the list in place", this looks like the cleanest solution. As some have mentioned, you don't want to iterate over the same list you're modifying. – John Gaines Jr. May 16 '11 at 20:41
9

Ok, but it seems not to be performing well at all. Won't this be O(n^2)? (And that is not counting the initial list copy). Removing the element on the fly would be O(n). – Scrontch May 16 '11 at 20:52
1

Scrontch - the only performance hit is from copying the list, you're still removing the element 'on the fly' - the inner code references `somelist` which is the original list. – bluepnume May 16 '11 at 20:55
4

using map (or list comprehensions) for side effects and throwing away the result is not very pythonic – John La Rooy May 16 '11 at 21:40
@Scrontch, O(n^2)+O(n) is still O(n^2). `list.remove()` is O(n) and it is in the loop, so removing in the loop _is_ O(n). This is one reason why 2 passes are better, they can easily both be O(n), and O(n)+O(n) is of course still O(n) – John La Rooy May 16 '11 at 21:44
-1. For reasons noted by gnibbler, code is not pythonic and unnecessary slow. I wouldn't have down-voted except that I feel the 4 up-votes need to be offset. Riccardo Galli, Mark Ransom, and gnibbler have better answers and all have less votes. – Steven Rumbalski May 17 '11 at 15:18
3

The alternative implementation is wrong. You will need to reverse 'toremove' before the map function. Otherwise later indices point to wrong objects. – akkishore Nov 22 '12 at 11:51
13

This seems pretty broken, `list.remove` removes the first occurrence of a value by equality, if you were trying to remove all float values from `[0, 1, 1.0, 0]` just by doing `.remove(0.0)` etc. you would end up with `[1.0, 0.0]` which is definitely **not** the result with all float removed. – Tadhg McDonald-Jensen Oct 30 '16 at 23:58

John Machin · Answer 2 · 2011-05-16T23:50:16.043

147

To meet these criteria: modify original list in situ, no list copies, only one pass, works, a traditional solution is to iterate backwards:

for i in xrange(len(somelist) - 1, -1, -1):
    element = somelist[i]
    do_action(element)
    if check(element):
        del somelist[i]

Bonus: Doesn't do len(somelist) on each iteration. Works on any version of Python (at least as far back as 1.5.2) ... s/xrange/range/ for 3.X.

Update: If you want to iterate forwards, it's possible, just trickier and uglier:

i = 0
n = len(somelist)
while i < n:
    element = somelist[i]
    do_action(element)
    if check(element):
        del somelist[i]
        n = n - 1
    else:
        i = i + 1

edited May 16 '11 at 23:50

answered May 16 '11 at 23:30

John Machin

81,303
11
141
189

26

You could also use `reversed(range(len(somelist)))` to make it look a bit nicer – Ben Ruijl Feb 20 '14 at 22:02
5

it is quadratic algorithm (`O(n**2)`). Here's a [linear solution if there are many elements to remove](http://stackoverflow.com/a/2794519/4279) and you don't want to use [list comprehension](http://stackoverflow.com/a/1207461/4279) for any reason. – jfs Nov 27 '16 at 15:00
1

Is this documented/defined behavior, or is it undefined behavior that happens to work (for now)? – Baruch Aug 14 '18 at 11:24

Zach Kelling · Answer 3 · 2011-05-16T21:15:45.593

13

List comp:

results = [x for x in (do_action(element) for element in somelist) if check(element)]

edited May 16 '11 at 21:15

answered May 16 '11 at 20:20

Zach Kelling

52,505
13
109
108

but the OP wants to call the "check" function **after** calling do_action – Riccardo Galli May 16 '11 at 20:30

John La Rooy · Answer 4 · 2011-05-16T23:45:10.333

11

for element in somelist:
    do_action(element)
somelist[:] = (x for x in somelist if not check(x))

If you really need to do it in one pass without copying the list

i=0
while i < len(somelist):
    element = somelist[i] 
    do_action(element)
    if check(element):
        del somelist[i]
    else:
        i+=1

edited May 16 '11 at 23:45

answered May 16 '11 at 20:16

John La Rooy

295,403
53
369
502

2

Also you could use a generator expression, then no temporary list is built: `somelist[:] = (x for x in somelist if not check(element))` – pillmuncher May 16 '11 at 20:45
-1 Elementary code review says "Doesn't work". – John Machin May 16 '11 at 23:31
@John, ah well the idea was there. That's what I get for writing untested code at 6:30 before my coffee – John La Rooy May 16 '11 at 23:39

Riccardo Galli · Answer 5 · 2012-02-13T12:18:53.293

7

You can still use filter, moving to an outside function the element modification (iterating just once)

def do_the_magic(x):
    do_action(x)
    return check(x)

# you can get a different filtered list
filter(do_the_magic,yourList)

# or have it modified in place (as suggested by Steven Rumbalski, see comment)
yourList[:] = itertools.ifilter(do_the_magic, yourList)

edited Feb 13 '12 at 12:18

answered May 16 '11 at 20:20

Riccardo Galli

12,419
6
64
62

2

Your arguments to `filter` are in the wrong order. Also, he wants the list modified in place, so use `itertools.ifilter` and assign to a slice: `yourList[:] = itertools.ifilter(do_the_magic, yourList)` – Steven Rumbalski May 17 '11 at 01:19
thanks, fixed the order. I didn't notice the "in place" requirement – Riccardo Galli May 17 '11 at 07:31

score 4 · Answer 6 · answered Jun 12 '13 at 07:52

4

Another way of doing so is:

while i<len(your_list):
    if #condition :
        del your_list[i]
    else:
        i+=1

So, you delete the elements side by side while checking

answered Jun 12 '13 at 07:52

Aswin Murugesh

10,831
10
40
69

score 2 · Answer 7 · answered May 16 '11 at 20:21

2

You can make a generator that returns everything that isn't removed:

def newlist(somelist):
    for element in somelist:
        do_action(element)
        if not check(element):
            yield element

answered May 16 '11 at 20:21

Mark Ransom

299,747
42
398
622

Except the OP want the list modified in place, presumably there are other references to it, so creating a filtered copy doesn't solve the whole problem. – PaulMcG May 17 '11 at 05:34
@Paul, it's a little unfair to judge by criteria that weren't part of the original question. The hard requirement to do the update in-place came in a comment after I gave this answer. – Mark Ransom May 17 '11 at 13:16
true, I see this all the time with the parsing questions. There is a process of discovery, since the original question usually leaves out 1 or 12 (or 12!) vital bits of information. – PaulMcG May 17 '11 at 13:21
To make this in-place assign to a slice: `somelist[:] = (x for x in newlist(someList))` – Steven Rumbalski May 17 '11 at 15:30

score 0 · Answer 8 · answered Jun 12 '13 at 10:51

Not exactly in-place, but some idea to do it:

a = ['a', 'b']

def inplace(a):
    c = []
    while len(a) > 0:
        e = a.pop(0)
        if e == 'b':
            c.append(e)
    a.extend(c)

You can extend the function to call you filter in the condition.

score 0 · Answer 9 · edited May 23 '17 at 12:34

Why not rewrite it to be

for element in somelist: 
   do_action(element)  

if check(element): 
    remove_element_from_list

See this question for how to remove from the list, though it looks like you've already seen that Remove items from a list while iterating

Another option is to do this if you really want to keep this the same

newlist = [] 
for element in somelist: 
   do_action(element)  

   if not check(element): 
      newlst.append(element)

Python: Removing list element while iterating over list

9 Answers9

Linked

Related