Оба хранят последовательности, но имеют противоположные профили затрат. Массив — это смежная память с индексацией O(1); связный список — это рассеянные узлы, соединённые указателями, с O(1) вставкой/удалением на концах, но без индексации.
Оба хранят последовательности, но имеют противоположные профили затрат. Массив — это смежная память с индексацией O(1); связный список — это рассеянные узлы, соединённые указателями, с O(1) вставкой/удалением на концах, но без индексации.
Библиотека вопросов для IT-собеседований с подробными ответами — от Junior до Senior.
Поддержать| Операция | Массив (динамический) | Связный список |
|---|
| Доступ по индексу | O(1) | O(n) |
| Поиск | O(n) | O(n) |
| Вставка/удаление в начале | O(n) | O(1) |
| Вставка/удаление в конце | O(1) амортизированно | O(1) с tail ptr |
| Вставка/удаление в середине | O(n) | O(n) поиск + O(1) splice |
| Затраты памяти | низкие | высокие (указатель на узел) |
| Локальность кэша | отличная | плохая |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
На практике массивы побеждают большую часть времени, потому что локальность кэша перевешивает различия Big-O для типичных размеров.
Знание обоих позволяет обосновать выбор на собеседованиях вместо слепого выбора — и объяснить почему "O(1) вставка" редко превосходит смежный массив.