Связный список хранит элементы иначе: каждый узел содержит значение и ссылку на следующий узел. Узлы разбросаны по памяти и связаны цепочкой.
[10|→] -> [20|→] -> [30|null]
Сильная сторона — вставка и удаление: чтобы добавить или убрать узел, достаточно переставить пару ссылок — O(1) (если узел уже на руках). Сдвигать ничего не нужно.
Слабая сторона — доступ по индексу. Чтобы добраться до пятого элемента, надо пройти по ссылкам от начала — O(n). Прямого «прыжка» по адресу, как в массиве, нет.
Сравнение помогает выбирать структуру под задачу: • нужен быстрый доступ по индексу и перебор → массив; • нужны частые вставки/удаления в начале или середине → связный список.
Главный вывод раздела: у каждой структуры данных свои сильные и слабые операции. Выбор структуры — это выбор того, какие операции должны быть быстрыми.