Связные списки

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

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

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

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q : TPoint;

Определен новый тип TPoint – ссылка на объекты типа TElement, причем TElement – это запись, имеющая два поля: Inf - целого типа и Next - типа TPoint. Здесь мы впервые сталкиваемся с ситуацией, когда в правой части определения для типа TPoint встречается имя типа TElement, который определен позже. В Паскале разрешается такое рекурсивное определение типов, если один из них является ссылочным.

Таким образом, переменные head и q типа TPoint являются записями, одно из полей которых содержит ссылку на адрес ячейки памяти, отводимой для переменной этого же типа. Значит, каждый элемент создаваемого списка будет содержать ссылку на такой же элемент списка. Признаком того, что данный элемент является последним в списке, является равенство поля ссылки этого элемента значению Nil – пустой ссылки. На каждый элемент списка, кроме первого, имеется ссылка от предыдущего элемента. Поэтому при формировании любого списка необходимо вводить переменную, значение которой является ссылка на текущий первый элемент списка – голову списка. Такой переменной у нас является head. Если список еще не сформирован, то есть в нем нет ни одного элемента (пустой список), то значение этой переменной должно равняться Nil.

Построим список из трех элементов, содержащих числа 5, -3, -12 (причем 5 - голова, а -12 - хвост). Пусть в ссылочном поле переменной head всегда хранится адрес текущего первого элемента списка. Переменную q будем использовать для выделения с помощью оператора New(q) места в памяти для размещения очередного элемента списка.

В начале построения списка ни одного элемента в нем нет – список пуст, поэтому нет и его начала:

New(head);