Ответ

В Python списки (list) — изменяемые структуры, а кортежи (tuple) — неизменяемые.

list: При добавлении новых элементов (append, extend, insert) Python выделяет "с запасом" блоки памяти, чтобы минимизировать количество аллокаций при росте массива ("over-allocation strategy"). Удаление элементов (pop, remove) происходит быстро, но иногда может вызвать перераспределение памяти.
tuple: Размер кортежа постоянен, элементы нельзя изменить или добавить — это обеспечивает высокую скорость операций чтения и меньший расход памяти по сравнению со списками при хранении большого количества неизменяемых данных.

Пример, иллюстрирующий изменение list и tuple:

lst = [1, 2, 3]
lst.append(4)    # OK
lst[1] = 20      # OK

tup = (1, 2, 3)
tup[1] = 20      # TypeError

Производительность:

Списки отлично подходят для часто меняющихся коллекций.
Кортежи чуть быстрее, оптимальнее по памяти (за счёт постоянного размера и принципов хэширования), пригодны для ключей словарей, возвращаемых значений из функций (immutable data).

Вопрос с подвохом

Вопрос: Почему операции добавления элементов к списку обычно выполняются быстро (O(1)), если с точки зрения массива это должно приводить к перераспределению памяти?

Ответ:

Python реализует динамические массивы с "выделением лишней памяти" сразу для нескольких элементов. Поэтому append обычно занимает O(1), а перераспределение памяти происходит только при реальном исчерпании резервного блока.

Пример:

import sys
lst = []
for i in range(10):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))  # Размер памяти растёт не строго линейно

История

Пример 1

В одном проекте для ключей словаря использовали list. Разработчик не знал, что списки не хэшируются (mutability), что вызвало ошибку "TypeError: unhashable type: 'list'".

Пример 2

Разработчик часто создавал длинные списки, конкатенируя их через +. Это приводило к дополнительным копированиям массива и высоким накладным расходам по памяти и времени. Эффективнее было использовать append в цикле или генераторы.

Пример 3

В системе логирования для хранения временных меток выбрали кортежи, думая, что за счёт immutable будет быстрее. Но периодически возникала необходимость в модификации, что требовало постоянно создавать новые кортежи (copy-on-write) и приводило к замедлению работы по сравнению с использованием списков.