What is the algorithmic complexity of converting a collections.deque to python list?

Question

I'm trying to determine the complexity of converting a collections.deque object into a python list object is O(n). I imagine it would have to take every element and convert it into the list, but I cannot seem to find the implementation code behind deque. So has Python built in something more efficient behind the hood that could allow for O(1) conversion to a list?

Edit: Based off the following I do not believe it could be any faster than O(n) "Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead."

If it cannot access a middle node in O(1) time it will not be able to convert without the same complexity.

https://docs.python.org/3.2/library/collections.html#deque-objects Near the bottom above the example, it explains the access times. https://wiki.python.org/moin/TimeComplexity Explains the general operations time complexities. — Dominique Randolph, Sep 18 '18 at 20:56

score 2 · Answer 1 · answered Sep 18 '18 at 20:55

You have to access every node. O(1) time is impossible for that fact alone.

I would believe that a deque follows the same principles as conventional deques, in that it's constant time to access the first element. You have to do that for n elements, so the runtime to do so would be O(n).

score 0 · Answer 2 · answered Sep 18 '18 at 21:03

Here is the implementation of deque

However, that is irrelevant for determining complexity to convert a deque to list in python.

If python is not reusing the data structure internally somehow, conversion into a list will require a walk through the deque and it will be O(n).

What is the algorithmic complexity of converting a collections.deque to python list?

2 Answers2

Linked