Динамические списковые структуры

Очевидно, наиболее фундаментальной структурой в оперативной памяти следует считать массивы, но они имеют крайне неприятный недостаток — память под массив выделяется в полном объеме до начала выполнения программы, и размеры ее ограничены. Файлы, конечно, предоставляют уникальные возможности обработки больших объемов информации, однако работа с файлом напрямую пока выполняется непозволительно медленно.

В поисках решения проблемы быстрой обработки больших объемов данных были предложены динамические списковые структуры данных. Они характеризуются следующими особенностями:

¨ для отдельных элементов структуры память выделяется в тот момент, ко­гда в них появляется необходимость (а не сразу и одним блоком как для массивов);

¨ число элементов динамической списковой структуры заранее не объявляется и мо­жет изменяться от нуля до некоторого значения, определяемого специ­фикой соответствующей задачи или доступным объемом памяти;

¨ память, занимаемая структурой, не представляет собой непрерывную об­ласть, т. е. элементы могут быть разбросаны в памяти хаотическим об­разом;

¨ логическая последовательность элементов задается в явном виде с по­мощью одного или нескольких указателей, хранящихся в самих элемен­тах. Как правило, каждый элемент, кроме своего значения, хранит указа­тель на следующий элемент или на два соседних с ним элемента.

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

Другое дело — живая очередь (в магазине, железнодорожной кассе). Коли­чество человек в очереди постоянно меняется, люди приходят и уходят, но никакой неразберихи не происходит — каждый знает, за кем он стоит. Об­разуется связанная цепочка людей. Очевидно, кому-то из стоящих в очереди и пришла идея создания динамических структур данных.

Простая по своей сути идея оказалась не столь простой в реализации, по­этому дальнейший материал потребует повышенного внимания. Рассмотрим наиболее распространенную динамическую структуру, которая называется связанным списком. Связанный список — это такая структура данных, эле­ментами которой служат записи одного и того же формата, связанные друг с другом с помощью указателей, расположенных в самих элементах.

Приведем примеры различных списочных структур:

• a) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента (см. рис. 4.2. (a)). Очень удобно представлять таким списком стек и очередь.
• b) Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка (см. рис. 4.2. (b)). Этот список удобен для работы с деками.
• c) Бинарное дерево может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 4.2. (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.
• d) Для представления ориентированного графа можно использовать иерархические списки - комбинацию из двух различных линейных списков (см. рис. 4.2. (d): вершины задаются структурой, содержащей три поля, а дуги - два; справа показан орграф, представленный приведенной списочной структурой).