Массив и связный список: различия и O-сложность

Что такое массив

Массив — структура данных с последовательным хранением элементов. Благодаря этому можно быстро обратиться к элементу по индексу.

items = [10, 20, 30]
value = items[1]

Доступ к items[1] обычно имеет сложность O(1).

Что такое связный список

Связный список состоит из узлов. Каждый узел содержит значение и ссылку на следующий узел. В двусвязном списке есть ссылки и на предыдущий, и на следующий узел.

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

Сравнение операций

Операция	Массив	Связный список
Доступ по индексу	`O(1)`	`O(n)`
Поиск элемента	`O(n)`	`O(n)`
Вставка в начало	`O(n)`	`O(1)`
Удаление из начала	`O(n)`	`O(1)`
Вставка после известного узла	`O(n)`	`O(1)`
Добавление в конец	Обычно амортизированно `O(1)`	`O(1)` при ссылке на tail, иначе `O(n)`

Почему вставка в массив может быть O(n)

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

Когда что выбирать

Массив подходит, когда нужен быстрый доступ по индексу и хорошая локальность данных в памяти. Связный список может быть удобен при частых вставках и удалениях в известных позициях, но на практике часто уступает массивам из-за дополнительной памяти на ссылки и плохой cache locality.

Как ответить на собеседовании

Массив даёт доступ по индексу за O(1), но вставка в начало или середину обычно стоит O(n) из-за сдвига элементов. В связном списке доступ по индексу — O(n), зато вставка или удаление возле известного узла выполняются за O(1).

Что такое массив и связный список? В чём разница по O-сложности операций?