list.pop(0) vs. collections.dequeue
arnodel at googlemail.com
Sat Jan 23 13:24:32 CET 2010
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:
>> 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.
More information about the Python-list