time complexity of random access in deque in Pytho

Question

This question already has an answer here:

• How are deques in Python implemented, and when are they worse than lists? 5 answers

I am wondering about the time complexity of the get operation of deque in Python.

I know that it is implemented as a doubly link in Python. Does that mean that its time complexity is O(n)?

Answer 1

deque are implemented a little smarter than just doubly-linked lists. They're a doubly-linked list of blocks of Python objects, where the left and right sides may be incomplete blocks.

The Big-O cost of accessing in the middle is still O(n), but it has a constant divisor (implementation dependent, CPython 3.5 allocates blocks that can store 64 objects). So if your deque has 1000 members, accessing in the middle still involves only around 7-8 "linked list-style" traversals, not 500-some. If the deque is smallish (65 to 128 elements, depending on how the empty slots align with the head and tail blocks), then lookup of any element is equal cost.