Двухсторонние очереди в Python: как альтернатива спискам повышает производительность

[eigrad]

Недавно обнаружил, что не знаю как устроена deque. Оказывается это специальная структура данных (а я почему то лет 15 из своего опыта в программировании считал что там двусвязный список под капотом). Иногда название этой структуры данных переводят как "дека". Двусторонняя очередь это тоже название этой структуры? Мне кажется что в статье не хватает краткого описания ее устройства.

[Andrey_Solomatin]

Двух связанный список там всё таки есть. Просто не на один элемент а на несколько.

https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c#L31

[mayorovp]

Да, deque — это двусторонняя очередь.

Структурой данных она не является, это скорее контракт структуры данных. Деку можно делать на двусвязном списке или на массиве. А можно и на двусвязном списке массивов, чтобы собрать преимущества обоих вариантов.

[DmitrySukharev]

Да, deque == double-ended queue

[AirLight]

Подскажите, а где применяяются двусторонние очереди?

[OgurcovAnd]

Приветствую!

Мне кажется, что в "time_fifo_testing(n)" Python проводить какие-то оптимизации, потому как list должен делать pop n элементов за O(n^2)., Что на 10^5 элементов -> 10^10 операций никак не укладывается в ~ 1 секунду.

Асимптотическое частное Должно быть как раз порядка 10^5, а не 100.