Связный список является простейшим типом данных динамической структуры, состоящей из элементов (узлов). Каждый узел включает в себя в классическом варианте два поля:
- данные (в качестве данных может выступать переменная, объект класса или структуры и т. д.)
- указатель на следующий узел в списке.
Элементы связанного списка можно помещать и исключать произвольным образом.
Доступ к списку осуществляется через указатель, который содержит адрес первого элемента списка, называемый корнем списка.
Классификация списков
По количеству полей указателей различают однонаправленный (односвязный) и двунаправленный (двусвязный) списки.
Связный список, содержащий только один указатель на следующий элемент, называется односвязным.
Связный список, содержащий два поля указателя – на следующий элемент и на предыдущий, называется двусвязным.
По способу связи элементов различают линейные и циклические списки.
Связный список, в котором, последний элемент указывает на NULL, называется линейным.
Связный список, в котором последний элемент связан с первым, называется циклическим.
Виды списков
Таким образом, различают 4 основных вида списков.
- Односвязный линейный список (ОЛС).
Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
- Односвязный циклический список (ОЦС).
Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
- Двусвязный линейный список (ДЛС).
Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
- Двусвязный циклический список (ДЦС).
Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.
Сравнение массивов и связных списков
| Массив | Список |
| Выделение памяти осуществляется единовременно под весь массив до начала его использования | Выделение памяти осуществляется по мере ввода новых элементов |
| При удалении/добавлении элемента требуется копирование всех последующих элементов для осуществления их сдвига | Удаление/добавление элемента осуществляется переустановкой указателей, при этом сами данные не копируются |
| Для хранения элемента требуется объем памяти, необходимый только для хранения данных этого элемента | Для хранения элемента требуется объем памяти, достаточный для хранения данных этого элемента и указателей (1 или 2) на другие элементы списка |
| Доступ к элементам может осуществляться в произвольном порядке | Возможен только последовательный доступ к элементам |
Назад: Структуры данных
Комментариев к записи: 2