[Tutor] why is list.pop(0) slow? [swap-with-last-element trick]

[Danny Yoo]

> On Thu, 19 Jun 2003, Wari Wahab wrote:
>
> > I've been playing around with very large lists and found out by chance
> > that pop(0) is 8 times slower than pop(). Is it really that bad?

Hi Wari,


By the way, if the order of your elements is not important, then there's a
cute trick we can employ to remove elements from the front of a list: we
can swap the first and last elements, and then do a pop() off then end of
our list, because popping at the end is quite efficient.


###
>>> def removeFront(L):
...     L[-1], L[0] = L[0], L[-1]
...     return L.pop()
...
>>> mylist = range(10)
>>> mylist
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> removeFront(mylist)
0
>>> mylist
[9, 1, 2, 3, 4, 5, 6, 7, 8]
>>> removeFront(mylist)
9
>>> mylist
[8, 1, 2, 3, 4, 5, 6, 7]
###

We can generalize this swap-with-last-element trick to do "deletes"
anywhere in our list.  Notice, though, that the list will inevitably get
out of order when we do the swap-with-last-element trick: the
applicability of this technique really depends on the program we're
writing.  It might not be the right thing to do if we want to maintain the
relative order of things in our list.


If you can tell us more details about what you're expecting to do with
your lists (lots of deletes, lots of inserts, etc.), we can probably chat
about efficiency issues on Python-Tutor.