17

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)?

intboolstring
  • 6,891
  • 5
  • 30
  • 44
DSKim
  • 575
  • 1
  • 6
  • 16
  • 1
    Also note documentation ["Indexed access is O(1) at both ends but slows to O(n) in the middle."](https://docs.python.org/3/library/collections.html#collections.deque.maxlen) – metatoaster Sep 16 '16 at 02:06
  • @metatoaster Python 3.5 introduced [index](https://docs.python.org/3/library/collections.html#collections.deque.index) for `deque`, but there's no mention of time complexity. – Abhijit Sarkar Jul 11 '23 at 10:40
  • @AbhijitSarkar It is a linear search through the queue for _x_, much like [`list.index`](https://stackoverflow.com/questions/5913671/complexity-of-list-indexx-in-python). As the way it is documented, it strongly implies searching. – metatoaster Jul 11 '23 at 12:22

1 Answers1

27

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.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • Really like these smart implementations ^_^ – zhy Dec 03 '21 at 16:27
  • @zhy: Yeah; downside to this implementation is you can't do zero-copy transfers of nodes from between `deque`s (linked lists could), and insertion/removal in the middle is `O(n)` element *moves*, not just `O(n)` node *traversals*. C++ allows stuff like that with `std::list`, but C++'s iterator design makes such node transfers "natural" w/o adding on non-standard API. Python's iterator protocol doesn't include the features needed to enable that, so you'd have to hack on non-standard stuff to enable linked list features; if you can't use linked list features anyway, `deque` is strictly better. – ShadowRanger Dec 03 '21 at 18:29
  • Specifically, the problem is that while C++'s iterator protocol lets you know both what the value is at the current position without advancing the iterator, and for most sequence iterators, allows you to move the iterator forward and backwards, Python's only offers one feature: Tell you the next value and advance the iterator (similar to doing `if (it != std::end(seq)) return *it++;` in C++); iterators represent the iteration of values themselves, not true positions in the sequence. – ShadowRanger Dec 03 '21 at 18:33