Чем отличается динамический массив (list в Python) от связанного списка?

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

Динамический массив (Dynamic Array), как list в Python:

Хранение: Элементы хранятся в непрерывном блоке памяти.
Доступ: Очень быстрый доступ к элементу по индексу (O(1)), так как его адрес легко вычислить (базовый_адрес + индекс * размер_элемента).
Вставка/Удаление: Медленные операции в середине или начале (O(n)), так как требуют сдвига всех последующих элементов.

Связанный список (Linked List):

Хранение: Элементы (узлы) хранятся вразнобой в памяти. Каждый узел содержит данные и указатель на следующий узел.
Доступ: Медленный доступ по индексу (O(n)), так как необходимо последовательно пройти по всем узлам от начала.
Вставка/Удаление: Очень быстрые операции (O(1)), если известен узел, после которого/перед которым нужно совершить действие. Требуется только изменить указатели у соседних узлов.

Операция	Динамический массив (`list`)	Связанный список
Доступ по индексу `arr[i]`	`O(1)` (быстро)	`O(n)` (медленно)
Вставка/удаление в конце	`O(1)` (амортизированно)	`O(n)` или `O(1)`*
Вставка/удаление в начале/середине	`O(n)` (медленно)	`O(1)`** (быстро)
Затраты памяти	Ниже (только данные)	Выше (данные + указатель)

*Если есть указатель на последний элемент (хвост). **Если известен узел, с которым производится операция.

class Node:
    def __init__(self, data=None):
        self.data = data  # Данные узла
        self.next = None  # Указатель на следующий узел

Динамический массив (list) — выбор по умолчанию для большинства задач. Идеален, когда требуется частый доступ к элементам по индексу и итерация по всей коллекции.
Связанный список — используется в специфических случаях, когда критически важны частые и быстрые вставки/удаления элементов в произвольные места списка (например, при реализации некоторых видов очередей, стеков или LRU-кэша).