Чем массив отличается от связного списка?

Массив хранит элементы в непрерывном куске памяти. Адрес i-го элемента вычисляется арифметикой: начало + i × размер элемента. Поэтому:

• доступ по индексу — O(1);
• добавление в конец динамического массива — амортизированно O(1);
• вставка и удаление в середине — O(n): нужно сдвинуть все элементы правее;
• поиск значения — O(n), в отсортированном — O(log n) бинарным поиском.

Связный список хранит каждый элемент в отдельном узле со ссылкой на следующий (в двусвязном — и на предыдущий). Узлы разбросаны по памяти.

• доступ к i-му элементу — O(n): нужно пройти по ссылкам;
• вставка и удаление, если узел уже найден, — O(1): поменять ссылки;
• вставка в начало — O(1);
• дополнительная память на ссылки в каждом узле.

Практика. Процессор читает память блоками и кэширует их. Массив читается подряд и попадает в кэш почти идеально, а переходы по узлам списка вызывают промахи кэша. Поэтому даже там, где по О-большому список выигрывает, массив на реальном железе часто быстрее. Связные списки используют, когда нужны стабильные ссылки на элементы и частые вставки или удаления по уже известной позиции: LRU-кэш (хеш-таблица + двусвязный список), очереди задач в ядре ОС.

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

# вставка после известного узла — O(1)
def insert_after(node, value):
    node.next = Node(value, node.next)

# доступ по индексу — O(n)
def get(head, i):
    while i > 0:
        head, i = head.next, i - 1
    return head.value