🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Как collections.deque хранит элементы блоками
У deque два конца, поэтому легко представить узел на каждый объект. В CPython звено списка хранит блок до 64 элементов. Соседние блоки связаны в обе стороны, а индексы указывают на первый и последний элементы.
При append и pop внутри блока меняются индекс и ячейка. Новый блок нужен, лишь когда крайний заполнен; опустевший крайний блок отсоединяется. Поэтому интерпретатор реже выделяет и освобождает память, чем при отдельном узле на элемент, и deque работает быстрее.
В разборе на mathspp.com эта механика собрана в упрощённой Python-реализации для Python 3.15. По коду можно проследить append и pop; левый край устроен симметрично.