Какие основные различия между массивами (array) и связными списками (linked list)?

Дополнительные вопросы:

1. В чем разница между ними в отношении использования памяти и доступа к их элементам?
2. В каких сценариях вы бы выбрали один вариант вместо другого для бэкэнд-приложения?

Подсказки:

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

Выше ожиданий:

• Анализ временной сложности для наихудших сценариев в обеих структурах данных.
• Понимание проблем фрагментации памяти с массивами по сравнению с накладными расходами памяти на указатели в связных списках.
• Варианты реализации, такие как двусвязные списки, циклические списки и динамические массивы (ArrayList/Vector).

Массивы:

• Выделяются в виде непрерывного блока памяти под элементы
• Размер фиксированный в большинстве языков (статические массивы)
• Требуют полного перевыделения памяти при изменении размера, то есть пересоздания массива
• Эффективны с точки зрения памяти (нет накладных расходов на элемент)

Связанные списки:

• Выделяются как отдельные узлы, разбросанные по памяти
• Каждый узел содержит данные и указатель(и) на другие узлы
• Не требуется перевыделение памяти при добавлении/удалении элементов
• Накладные расходы на указатели (4-8 байт на узел)

Массив:      [1][2][3][4][5]  (смежная память)
Связанный список: [1|•]-->[2|•]-->[3|•]-->[4|•]-->[5|⌀]  (разбросанная память)

Временная сложность

• *Если существует указатель на хвост
• **O(1) если существует ссылка на предыдущий узел

Когда следует выбирать массивы

• Когда часто используется случайный доступ (получение элементов по индексу)
• Когда память ограничена и важны накладные расходы
• Когда размер данных известен или относительно стабилен
• Для кэшей (пространственная локальность)
• В численных вычислениях или операциях с матрицами
• При реализации стеков с ограниченным размером

Когда следует выбирать связанные списки

• Когда часто происходят вставки и удаления
• Когда размер сильно варьируется или непредсказуем
• Когда фрагментация памяти является проблемой
• Для реализации стеков, очередей или кэшей LRU
• Когда выделение памяти должно происходить по частям

Вариации структур

Массивы:

• Динамические массивы (ArrayList в Java, список в Python)
• Многомерные массивы

Связанные списки:

• Односвязные (только вперёд)
• Двусвязные (двусторонний проход)
• Циклические связанные списки (последний узел указывает на первый)