Что хотят услышать интервьюеры:

Массив и связный список решают похожую задачу хранения последовательности элементов, но делают это по-разному. У массива быстрее доступ по индексу и лучше работа с памятью, у связного списка проще вставки и удаления в середине, если уже есть нужный узел. На собеседовании важно показать понимание компромисса между скоростью доступа и стоимостью модификаций.

Определение:

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

Главное отличие в том, что у массива есть прямой доступ к элементу по позиции, а у связного списка — последовательный проход от начала. Из-за этого массив обычно удобнее для чтения по индексу, а связный список — для частых вставок и удалений внутри последовательности.

Пример использования:

Если нужно часто брать элемент по номеру, например users[500], обычно удобнее массив. Если нужно постоянно вставлять и удалять элементы в середине очереди, а список часто меняется, связный список может быть выгоднее.

# Массив/список в Python
arr = [10, 20, 30, 40]
print(arr[2])  # 30

# Условный связный список
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

head = Node(10, Node(20, Node(30)))

current = head
while current:
    print(current.value)
    current = current.next

Пояснение кода:

В первом примере используется обычный список Python, который по сути ведёт себя как динамический массив: к элементу arr[2] можно обратиться напрямую по индексу.

Во втором примере показан простой односвязный список:

Node хранит значение и ссылку на следующий узел.
head — это начало списка.
Чтобы пройти по списку, нужно идти от head к next, пока узлы не закончатся.
Доступ к третьему элементу требует последовательного прохода через предыдущие узлы.

Ключевые моменты:

У массива доступ по индексу обычно быстрый: O(1).
У связного списка доступ к i-му элементу обычно требует прохода: O(n).
Вставка и удаление в массиве могут быть дорогими из-за сдвига элементов.
В связном списке вставка/удаление после найденного узла обычно проще, но сам поиск узла стоит времени.
Массив лучше использует память за счёт непрерывного размещения элементов.
Связный список тратит больше памяти на хранение ссылок между узлами.

Какие основные отличия между массивом и связным списком в структуре данных?