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