Здесь описана сложность исполнения основных операций над списками.
Под капотом списки представлены в виде массивов. Наибольшие затраты происходят при необходимости дополнить список (когда изначально выделенной под него памяти недостаточно, все элементы придётся переместить в другое место), либо при вставке/удалении элемента близко к началу (последующие элементы потребуется переместить назад).

На заметку
Если требуется оптимизированная возможность вставки/удаления с обоих концов, вместо списков используйте collections.deque.

На заметку
Общие для списков и кортежей операции имеют одинаковую сложность.

Далее n — количество элементов в контейнере; k — значение параметра, либо количество элементов в параметре.

Обращение по индексуO(1)l[i]
ПрисвоениеO(1)l[i] = 0
lenO(1)len(l)
.appendO(1)l.append(5)
.popO(1)l.pop()То же что и l.pop(-1) — выброс с конца.
.clearO(1)l.clear()
СрезO(b-a)l[a:b]
.extendO(k)l.extend(a)
СозданиеO(k)list(a)
Проверки ==, !=O(n)l1 == l2
.insertO(n)l.insert(0, 5)
delO(n)del l[i]То же и с удалением среза.
.removeO(n)l.remove(...)
Проверка на входимостьO(n)x in lПроход по списку.
.copyO(n)l.copy()То же что и l[:].
.popO(n)l.pop(i)
min, maxO(n)min(l)
.reverseO(n)l.reverse()
ПроходO(n)for v in l:
Присвоение срезаO(k+n)l[... : ...] = ...
.sortO(n log n)l.sort()
УмножениеO(k×n)i l

Синонимы поиска: Сложность операций со списками
На заметку
У нас есть представительство в Facebook. Ссылка в самом низу страницы.