Arnaud Delobelle 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.
Your assumption is correct. The collections.dequeue type uses a double linked list of blocks. Each blocks contains a fixed amount of pointers to Python objects. The implementation makes the implementation less memory hungry than a standard double linked list with just one element for each block. Christian -- http://mail.python.org/mailman/listinfo/python-list
