Однонаправленный список

Для создания списка определяется структурный тип T,
на языке Pascal:

Type T = ^Rec;
   Rec = Record
           info  : integer;   {Информационное поле}
           next : T;         {Ссылка на следующую запись}
         End;

на языке С++:

struct T
{
  int   info1;
  char  info2[20];
  T   * next;
};

В структуре Т имеется одно поле next, объявленное как указатель на T. Другие поля структуры содержат информацию, характеризующую элемент списка.

При образовании первого элемента ("корня") списка в поле next заносится пустой указатель ((nil или NULL).
При дальнейшем построении списка это значение будет присутствовать в последнем элементе списка:



Над списком, построенном в такой манере, можно выполнять операции поиска элемента, удаления элемента и занесение нового элемента в начало, конец или середину списка. Понятно, что все эти операции будут выполняться путем манипуляций над содержимым поля next существующих элементов списка. Для оптимизации операций над списком иногда создают вспомогательную переменную-структуру (заголовок списка), состоящую из двух полей – указателей на первый и последний элементы списка. Для этих же целей создают двунаправленные списки, элементы которых, помимо поля next, включают поле previous, содержащее указатель на предыдущий элемент списка и, возможно, ссылки на заголовок списка.