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

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

Рисунок 1. Структура данных – линейный список

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

В следующем листинге показано, как можно определить структуру данных линейный связный список. Использованы функции new(x) – которая для переменной x выделяет память, соответственно необходимому размеру, т.е. количеству байт, которое занимает представление типа переменной x в памяти ЭВМ. После вызова new(x) в x записывается адрес выделенной области памяти. Процедура dispose(x) – освобождает выделенную для переменной x память. По завершению программы вся выделенная память должна быть возвращена системе.

Листинг 3. Объявление и использование связного списка

program listing_3;
uses crt; (* подключаем библиотеку *)
type 
  a = ^b; {тип - указатель на элемент списка}
  b = record {тип – элемент списка}
        x: Integer;
        next: a; {указатель на следующий}
      end;
var
  head {голова списка}, tmp: a;    
begin
 clrscr; (* очистка экрана *)
 new(head); {выделение памяти для 1го элемента}
 head^.x := 10; { заполняем поле x значением 10 }
 head^.next := nil; {пустой указатель} 
 new(tmp);	{ выделение памяти для 2го элемента }
 tmp^.x := 11;  tmp^.next := nil;
 head^.next := tmp; {связывание со вторым элементом}
 new(tmp); { выделение памяти для 3го элемента }
 tmp^.x := 12;  tmp^.next := nil;
 head^.next^.next := tmp; {связывание с третьим элементом, 
                   т.е. с следующим для следующего за первым} 
{далее выводим элементы списка и освобождаем память:}
 tmp := head;
 while not(tmp = nil) do begin
   writeln(tmp^.x); {печать значения}
   tmp:=tmp^.next; {переход к следующему элементу}
   dispose(head); {освобождение памяти}
   head:=tmp
 end
end.