Массив хранит элементы в смежных ячейках памяти, обеспечивая быстрый доступ по индексу (O(1)). Размер фиксирован при создании.
Связанный список хранит элементы в узлах, каждый из которых содержит данные и ссылку на следующий узел. Доступ к элементу по индексу требует обхода (O(n)). Размер динамический.
Основные различия:
| Признак | Массив | Связанный список |
|---|---|---|
| Размещение | Смежные ячейки памяти | Узлы со ссылками |
| Доступ по индексу | Быстрый (O(1)) | Медленный (O(n)) |
| Вставка/удаление | Медленное (O(n)) | Быстрое (O(1)) в начале/конце списка |
| Размер | Фиксированный | Динамический |
Пример добавления элемента в массив требует создания нового массива и копирования элементов:
javaПример добавления элемента в связанный список (в конец):
java