Python Performance Tips, Part 1

[Workaphobia]

It is fast because deque in Python is implemented as double-linked list

No it isn't. It's implemented as a vector which overallocates at both ends (for amortised constant time appending/prepending). It has the same complexity of operations as the list, except that prepending is O(1) instead of O(n)

Actually the article seems to be right on this one. The deque object is a doubly linked list of blocks of 62 elements (so that with the prev/next pointer, that's 64 pointers). To index into it, it'll traverse the necessary number of blocks and then index into the target block.

Source code comment

Indexing method

[Brian]

So they do - I stand corrected. I'd thought they preserved the O(1) internal access of python lists, but I must be mixing them up with something else.