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

Список – это динамическая структура данных, представляющая собой некоторое множество однородных элементов, связанных друг с другом только отношением следования. Элементы списка – всегда динамические переменные, а связь элементов списка обеспечивается переменными типа «указатель на элемент». Число элементов в списке может быть любым; в частности список может быть пустым, то есть не содержать ни одного элемента.

Вначале приведем ряд определений.

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

§ Линейный список – это динамическая структура данных, которая представляет собой совокупность линейно связанных элементов, для которых разрешается добавлять элементы между любыми двумя другими и удалять любой элемент.

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

§ Односвязный список – это список, в котором каждый элемент связан («знает» о местонахождении) только с одним, следующим за ним элементом.

§ Двухсвязный список – это список, в котором каждый элемент связан с двумя соседними для него элементами, как находящимся перед, так и находящимся после него.

По типу доступа к элементам списка различают очереди и стеки:

§ Очередь – это частный случай линейного списка, для которого добавление нового элемента разрешено только в конец списка, а удаление – только из начала (из головы) списка.

§ Стек – это частный случай линейного списка, для которого добавление нового элемента и удаление существующего всегда производится только из начала списка. Голову такого списка часто называют вершиной стека.

Приведем графические иллюстрации списков (здесь приведены частные примеры организации списков):

а) Линейный односвязный список (Head – переменная-указатель на первый элемент или голову списка; Tail – переменная-указатель на последний элемент списка; Info – область элемента, в которой хранится полезная информация)