Односвязные линейные списки – это данные динамической структуры, состоящие из однородных элементов, линейно связанных между собой.
Для них определены следующие действия:
• Добавление элемента в начало (голову) списка;
• Добавление элемента в конец (хвост) списка;
• Вставка элемента между двумя любыми другими элементами списка;
• Удаление любого элемента списка.
Каждый элемент списка состоит из данных и ссылки на следующий элемент списка. На первый элемент списка и тем самым на весь список указывает переменная-указатель. Последний элемент содержит пустую ссылку 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;
Проходы по списку
Проходом называют посещение всех элементов списка, начиная с головы списка.
