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

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

Для них определены следующие действия:

• Добавление элемента в начало (голову) списка;

• Добавление элемента в конец (хвост) списка;

• Вставка элемента между двумя любыми другими элементами списка;

• Удаление любого элемента списка.

Каждый элемент списка состоит из данных и ссылки на следующий элемент списка. На первый элемент списка и тем самым на весь список указывает переменная-указатель. Последний элемент содержит пустую ссылку nil.

Для представления элементов списка используют записи, например: type ref =^Elem; Elem=record inf: integer; next: ref end; Тип ref – это указатель на переменные базового типа Elem

 

Замечание: при описании указательных типов разрешается в правой части равенства указывать идентификатор базового типа (здесь Elem), который еще не описан, но тогда его описание должно быть сделано в этом же разделе описания типов type.

Для сохранения информации о списке достаточно одной статической переменной – указателя на первый элемент этого списка (обычно его называют головой списка).

С указателем на голову списка нельзя производить никаких действий, которые могут стать причиной утери всего списка. Для работы со списком обычно заводят вспомогательный указатель, копируя в него ссылку на голову списка, например: p:=Head.

Для доступа к элементам списка будем использовать следующие конструкции:

p – адрес текущего элемента списка;

p^ – запись из двух полей, хранящаяся по адресу p;

p^.inf – первое поле этой записи;

p^.next – второе поле этой записи, являющееся адресом следующего элемента списка;

p^.next^.inf – первое поле элемента списка, следующего за тем, на который указывает р;

p^.next^.next – второе поле элемента списка, следующего за тем, на который указывает р.

Основные действия над односвязными линейными списками

При описании действий используются следующие переменные:

var Head,p,pred,q,pmax:ref;

x,A,tmp:integer;

Создание пустого списка

Head:=nil

Вставка элемента в начало списка

Исходный список	Список после вставки элемента

new(q); //Выделение в динамической памяти места для нового элемента

q^.inf:=x; //Заполнение поля данных

q^.next:=Head; //Заполнение поля ссылки

Head:=q; //Присоединение нового элемента к началу списка

Удаление первого элемента

Исходный список	Список после удаления первого элемента

p:=Head; //Установка текущего указателя на начало списка

Head:=p^.Next;//Установка Head на элемент, следующий за первым

Dispose(p); //Освобождение памяти, которую занимал первый элемент

p:=nil;

Проходы по списку

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