Remove items from a list

[Alex Martelli]

Dan Perl <dperl at rogers.com> wrote:

> But Stan says he tried something like that (see the comment in his code) and
> it was still not working.  I would still need a more complete code example
> to reproduce the problem and figure out what went wrong.

Stan was not looping backwards through the list, which as Mel indicated
is a crucial part of making this clunky idiom "work" (sorta...):

> >    The way to remove items from a list is (untested code):
> >
> >         for i in xrange (len (a_list)-1, -1, -1):
> >             if i_want_to_remove (a_list[i]):
> >                 del a_list[i]
> >
> > Going through the list backwards means that deleting an item
> > doesn't change the index numbers of items we've yet to

If you can make this work, you'll end up with *horrible* performance;
assuming that on average you're removing a number of items proportional
to len(a_list), this loop has O(N^2) performance.

That's because a Python list is not a linked-list, but rather a
compact-in-memory array... so, while on one hand indexing L[x] is O(1)
[NOT O(x) as it would be in a linked list], insertions and deletions
somewhere inside the list _are_ O(len(L)), since all items following the
insertion or deletion point must be shifted ('down' for a deletion, 'up'
for an insertion) to keep the array compact in memory.

Building a new list with a list comprehension (or with 'filter') and
possibly assigning it to the same name as the old list (or as the
contents of the old list, without name rebinding) OTOH is O(N), so it's
clearly the right way to go.


Alex