Как устроен список в Python?

Список в Python — это упорядоченная, изменяемая коллекция элементов, основанная на динамическом массиве.

• Упорядоченный: Элементы хранятся и доступны по индексу.
• Изменяемый (mutable): Можно добавлять, удалять и изменять элементы после создания.
• Динамический массив: Список может увеличиваться или уменьшаться в размере по мере добавления/удаления элементов. Python управляет выделением памяти для массива автоматически.
• Разнородные типы: Список может содержать элементы различных типов данных (int, str, float, другие списки и т.д.) одновременно.
• Реализация в CPython: В стандартной реализации Python (CPython) список реализован как массив указателей на объекты Python. При изменении размера списка происходит перевыделение памяти и копирование элементов, что может быть неэффективно для частых операций добавления/удаления в начале или середине очень больших списков. Для таких случаев лучше использовать collections.deque.

# Пример создания и использования списка
my_list = [1, "hello", 3.14, [4, 5]]

# Доступ к элементам по индексу
print(my_list[0])  # Output: 1
print(my_list[-1]) # Output: [4, 5]

# Изменение элемента
my_list[1] = "world"
print(my_list)     # Output: [1, 'world', 3.14, [4, 5]]

# Добавление элемента
my_list.append(True)
print(my_list)     # Output: [1, 'world', 3.14, [4, 5], True]

# Удаление элемента
my_list.remove(3.14)
print(my_list)     # Output: [1, 'world', [4, 5], True]

# Длина списка
print(len(my_list)) # Output: 4

Операции сдвига (вставка или удаление в начале/середине) имеют сложность $O(n)$, где $n$ - длина списка, из-за необходимости сдвигать последующие элементы. Добавление в конец (append) обычно имеет амортизированную сложность $O(1)$, так как перевыделение памяти происходит не при каждой операции.

# Пример вставки элемента в начало (O(n))
my_list.insert(0, "start")
print(my_list)

# Пример удаления элемента по индексу (O(n))
del my_list[1]
print(my_list)