list.pop(0) vs. collections.dequeue

[Roy Smith]

In article 
<3ac173bd-4124-434d-b726-0b9baaeec752 at 36g2000yqu.googlegroups.com>,
 Steve Howell <showell30 at yahoo.com> wrote:

> In my case I'm not really concerned about giving the memory back right
> away, it's more about keeping my code simple.  Once I'm done with an
> element, I do just want to pop it off and keep all the simplicity of
> the lists, but I am just concerned enough speed that for a 1000
> element list, I don't want to be doing 1000 memmoves for an average of
> 500 pointers, which effectively moves about a million bytes around for
> no reason.

If you really want to pop all the elements from a long list, reverse the 
list and pop them off the end.  Popping every element off the beginning of 
the list is O(n^2), as you pointed out.  Reversing the list is O(n), and 
each pop after that is O(1), so the overall complexity is O(n).