Уроки 41 - 42
Списки
(§41. Списки)

Содержание урока

Что такое список?

Использование динамического массива

Модульность

Связные списки

Вопросы и задания

Задачи

Связные списки

Линейный список иногда представляется в программе в виде связного списка, в котором каждый элемент может быть размещён в памяти в произвольном месте, но должен содержать ссылку (указатель) на следующий элемент. У последнего элемента эта ссылка нулевая (в Паскале — nil), она показывает, что следующего элемента нет. Кроме того, нужно хранить где-то (в указателе Head) адрес первого элемента («головы») списка, иначе список будет недоступен (рис. 6.3).

Рис. 6.3

Если замкнуть связный список в кольцо, так чтобы последний элемент содержал ссылку на первый, получается циклический список (рис. 6.4).

Рис. 6.4

Поскольку элементы связного списка содержат ссылки только на следующий элемент, к предыдущему перейти нельзя. Поэтому перебор возможен только в одном направлении. Этот недостаток устранён в двусвязном списке, где каждый элемент хранит адрес как следующего, так и предыдущего элемента (рис. 6.5).

Рис. 6.5

Для такого списка обычно хранятся два адреса: «голова» списка (указатель Head) и его «хвост» (указатель Tail). Можно организовать и циклический двусвязный список. Использование двух указателей для каждого элемента приводит к дополнительному расходу памяти и усложнению всех операций со списком, потому что при добавлении и удалении элемента нужно правильно расставить оба указателя.

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

Следующая страница Вопросы и задания

Cкачать материалы урока