Односвязный и односвязный циклический списки

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

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

Рис. 1. Односвязный список. Логическая структура.

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

Логическая структура линейного односвязного списка:

Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель текущего элемента списка.

Логическая структура элемента линейного односвязного списка:

Данные или указатель на данные, указатель на следующий элемент списка.

Продвижение в линейном односвязном списке возможно только в одном направлении. Результаты выполнения операций включения элемента в линейный односвязный список и исключения элемента из линейного односвязного списка — линейный односвязный список.

связный список циклический логический.

Рис. 2. Выполнение операции включения элемента в линейный односвязный список.

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

Рис. 4. Кольцевой односвязный список. Логическая структура.