TIL #145 – collections.deque is implemented in blocks

Today I learned that collections.deque is implemented as a doubly-linked list of blocks. collections.deque I've written about the data structure deque from the module collections extensively. In particular, I wrote a deque tutorial with plenty of practical example use cases of deque. Today, after some discussion during a cohort I was teaching, a student sent a link to the collections.deque source code where a comment explains some of the lower-level details of how a deque is implemented. Double-ended queue The name “deque” stands for Double-Ended QUEue and that's because a deque is a doubly-linked list. When you learn about that, you might think that, under the hood, a deque is essentially a collection of nodes that link to the next and to the previous: class Node: prev_node: Node | None value: object next_node: Node | None class deque: first_node: Node | None last_node: Node | None ... But that's not the case. Apparently, a deque is implemented in a more optimised way, where each…