Уроки 71 - 73
Списки
(§41. Списки)
Содержание урока
Использование динамического массива
Связные списки
Связные списки
Линейный список иногда представляется в программе в виде связного списка, в котором каждый элемент может быть размещён в памяти в произвольном месте, но должен содержать ссылку (указатель) на следующий элемент. У последнего элемента эта ссылка нулевая (в Паскале — nil), она показывает, что следующего элемента нет. Кроме того, нужно хранить где-то (в указателе Head) адрес первого элемента («головы») списка, иначе список будет недоступен (рис. 6.3).
Рис. 6.3
Если замкнуть связный список в кольцо, так чтобы последний элемент содержал ссылку на первый, получается циклический список (рис. 6.4).
Рис. 6.4
Поскольку элементы связного списка содержат ссылки только на следующий элемент, к предыдущему перейти нельзя. Поэтому перебор возможен только в одном направлении. Этот недостаток устранён в двусвязном списке, где каждый элемент хранит адрес как следующего, так и предыдущего элемента (рис. 6.5).
Рис. 6.5
Для такого списка обычно хранятся два адреса: «голова» списка (указатель Head) и его «хвост» (указатель Tail). Можно организовать и циклический двусвязный список. Использование двух указателей для каждого элемента приводит к дополнительному расходу памяти и усложнению всех операций со списком, потому что при добавлении и удалении элемента нужно правильно расставить оба указателя.
Применение связных списков приводит к более сложным алгоритмам, чем работа с динамическими массивами; рассматривать соответствующие программы мы не будем.
Следующая страница 
Вопросы и задания
Cкачать материалы урока
