list.pop(0) vs. collections.dequeue

[Arnaud Delobelle]

Dave Angel <davea at ieee.org> writes:

> 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.

Yes you are correct.  This will teach me (again!) to check my facts.

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

I've just looked and it is a doubly-linked list of 'blocks' of size
BLOCKLEN, which is 62 on the source I have (I guess it's 62 because then
the whole block structure is 64 exactly, 62 + 1 for each link).  So a
small list will have near constant random access, in a way.

-- 
Arnaud