list.pop(0) vs. collections.dequeue

[Dave Angel]

Arnaud Delobelle wrote:
> Steve Howell <showell30 at yahoo.com> writes:
>
>   
>> On Jan 22, 12:14 pm, Chris Rebert <c... at rebertia.com> wrote:
>>     
>> <snip>
> I made the comment you quoted.  In CPython, it is O(n) to delete/insert
> an element at the start of the list - I know it because I looked at the
> implementation a while ago.  This is why collections.deque exists I
> guess.  I don't know how they are implemented but insertion/deletion at
> either end are O(1) and so is random access.  So they are the data
> structure that you want.
>
>   
Not according to the 2.6 docs.

Indexed access is O(1) at both ends but slows to O(n) in the middle. For 
fast random access, use lists instead.

That sounds to me like a doubly-linked list implementation.

<snip>