Dave Angel <da...@ieee.org> writes: > Arnaud Delobelle wrote: >> Steve Howell <showel...@yahoo.com> writes: >> >> >>> On Jan 22, 12:14 pm, Chris Rebert <c...@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 -- http://mail.python.org/mailman/listinfo/python-list
