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

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

• Массив — это непрерывный блок памяти, где элементы хранятся последовательно. Это позволяет быстро обращаться к элементам по индексу (операция доступа O(1)). Однако размер массива фиксирован, и добавление или удаление элементов в середине требует сдвига элементов, что дорого по времени (O(n)).

• Связный список состоит из узлов, каждый из которых содержит данные и ссылку на следующий узел. Элементы могут располагаться в памяти не подряд. Добавление и удаление элементов в списке происходит быстро (O(1)), если есть ссылка на нужный узел, но доступ к элементу по индексу требует последовательного обхода (O(n)).

Пример:

# Массив в Python (список)
arr = [1, 2, 3, 4]
print(arr[2])  # Быстрый доступ к элементу с индексом 2

# Связный список (упрощённый пример)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Доступ к элементу требует обхода
current = head
for _ in range(2):
    current = current.next
print(current.data)