Request to talk about how deque is implemented in Python

[bharatagarwal]

I've noticed a significant performance in the hot potato problem between using the naive implementation of Queue v/s the solution that uses collections.deque.

The naive implementation of Deque has similar performance issues, with insert and remove from left/rear requiring the whole array to move over.

CPython has an implementation using double linked lists, which could be worth talking about once the "Lists" section has been covered.

[bharatagarwal]

If doubly linked lists are out of scope for the book, might be worthwhile to add a note at the end of the hot potato problem, mentioning the performance difference and sharing the link to the CPython deque implementation as an exercise for the reader.

[robot-dreams]

Good idea! book/queues/implementation.md mentions the performance implications, but mentioning that collections.deque uses a doubly-linked list and linking to an implementation could be helpful. (BTW It could also be interesting to mention that in CPython the elements of the linked list are blocks, rather than single elements—it cuts down on the cache misses a bit.)

Please feel free to open a PR adding a sentence / link wherever you think is appropriate, maybe the end of book/deques/implementation.md?