list.pop(0) vs. collections.dequeue

[Christian Heimes]

Steve Howell wrote:
> I disagree that Python code rarely pops elements off the top of a
> list.  There are perfectly valid use cases for wanting a list over a
> dequeue without having to pay O(N) for pop(0).  Maybe we are just
> quibbling over the meaning of "rarely."

I was speaking from my own point of view. I've written several tenths of
thousands of lines of Python code in the last seven years, mostly
related to data manipulation, web applications and operating system
interaction but also GUI stuff and scientific code. I can't recall any
performance critical or prominent code that modifies the head of a list
a lot.

Of course there a use cases where you may want to use list.pop(). Unless
you need a FILO structure you can always replace a LILO with a FIFO --
instead of list.insert(0, value) and list.pop(0) use list.append(value)
and list.pop(). It's not possible to optimize a data structure for all
use cases.

> I am not proposing a linked list of pointers.  I am wondering about
> something like this:
> 
> p = &p[1];
> (and then reclaim p[0] as free memory, I already said I understood
> that was the tricky bit)
> 
> The pointer arithmetic for accessing each element would still work in O
> (1), right?

You mean it's an impossible trick unless you come up with your own
memory management system. Realloc(), the standard function to change the
size of chunk of allocated memory in C, doesn't support your desired
operation.

Christian