Связанный списокявляется простейшим типом данных динамической структуры. Компоненты связанного списка можно помещать и исключать произвольным образом [1,3,8,11]. Графическое представление связанного списка показано на рис. 2.1.
Элемент списка называется узлом. Каждый узел содержит два поля: поле информации info и поле следующего адреса ptrn. Поле адреса хранит указатель на следующий элемент. Доступ к списку осуществляется через указатель 1st, который содержит адрес первого элемента. Поле адреса последнего элемента хранит нулевое значение NULL. Пустой список инициализируется как 1st = NULL.
| 1st| | ptrn = | NULL | |||||||
| [nfo | ptrn | —^ | info | ptrn | ... —+■ | Info | ptrn| | ||
Рис. 2.1
Введем обозначения [11]: пусть р— указатель на элемент списка; тогда mfo(p) — ссылка на информационную часть элемента; ptrn(/?) — ссылка на адрес следующего элемента; р = getnode() — выделение участка оперативной памяти под элемент списка; freenode(p) — освобождение участка оперативной памяти, отведенного под элемент списка.