В чем разница между массивами и связанными списками?

Массивы и связанные списки — две из самых популярных линейных структур данных. Давайте посмотрим на некоторые из их основных различий:

Содержание

Массивы

Весь массив хранится в непрерывном блоке памяти.

Различные элементы хранятся в разных местах памяти.

Размер массива указывается во время объявления и не может быть изменен впоследствии.

Элементы данных могут быть добавлены или удалены из связанного списка по желанию.

Из-за непрерывного распределения массив может храниться только там, где доступен большой блок свободного пространства.

Различные элементы хранятся в разных местах; следовательно, связанные списки можно составлять на небольших участках свободного пространства.

В целом потребление места меньше.

Для хранения указателей рядом с узлами требуется место.

Любой элемент можно напрямую проиндексировать в O ( 1)O(1) O (1) время наихудшего случая.

Список необходимо пройти от первого элемента до требуемого элемента, принимая O ( n ) O (n) O (n) время наихудшего случая.

Линейный поиск и двоичный поиск (если отсортировано).

Только линейный поиск.