Какова сложность операции вставки у deque?

Question

[zlodiak]

Скажите пожалуйста, я правильно понимаю, что в python3 у очереди из collections.deque при вставке значения в середину очереди сложность вычисляется по O(1)?

Я так думаю потому что любая очередь это односвязный или двусвязный список. таким образом при вставке не требуется перебирать подряд все элементы, а просто создать элемент и привязать его указатели на соседние элементы

Comments

[Roman K]

Зачем когда-то может понадобиться вставлять в середину очереди?

Answer 1

[devalone]

> https://wiki.python.org/moin/TimeComplexity

> A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

из этого следует, что O(N). И даже если б это был обычный одно или дву связный список, то элемент, куда вставлять, ещё надо найти, а это O(N), если передаётся по индексу, а не указателю.

Answer 2

[Сергей Тихонов]

https://wiki.python.org/moin/TimeComplexity

collections.deque
A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

TLDR: "В середину" всё плохо.