Связанный список (Linked list)
Связанный список — структура данных состоящая из элементов соединённых ссылками. Каждый элемент списка содержит данные и ссылку на следующий элемент.
Для удобства использования списка, отдельно хранят ссылку head на первый элемент:
Добавление и удаление элементов
Добавление и удаление элементов зависит от положение элемента и делится на три случая:
- Добавление и удаление первого элемента;
- Добавление и удаление элемента в середине списка;
- Добавление и удаление элемента в начале списка.
При добавлении первого элемента ссылка-указатель на список устанавливается на первый элемент.
Использование памяти
Особенность связанного списка в том, что за счет того что он состоит из отдельных элементов, он не требует последовательного участка памяти для расположения элементов. Элементы списка могут находятся в любой позиции относительно друг друга, а связи между ними формируются на основе ссылок.
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 2. Сортировка выбором. Массивы и связанные списки