Какова скорость работы различных коллекций

В Python основные коллекции имеют разную асимптотическую сложность операций:

Списки (list)

• Доступ по индексу: O(1)
• Вставка/удаление в конце: O(1)
• Вставка/удаление в начале/середине: O(n)
• Поиск элемента: O(n)

lst = [1, 2, 3]
lst[0]  # O(1)
lst.append(4)  # O(1)
lst.insert(0, 0)  # O(n)

Множества (set) и словари (dict)

• Добавление/удаление: O(1) в среднем
• Поиск: O(1) в среднем
• Итерирование: O(n)

s = {1, 2, 3}
s.add(4)  # O(1)
3 in s  # O(1)

Кортежи (tuple)
Аналогичны спискам, но неизменяемые. Операции те же, кроме модификации.

collections.deque

• Добавление/удаление с обоих концов: O(1)
• Доступ к элементам в середине: O(n)

Выбор коллекции зависит от операций, которые будут выполняться чаще всего. Для частого поиска - set/dict, для FIFO/LIFO - deque, для произвольного доступа - list.