Формирование односвязного списка

Как правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру:

struct List

{

int info; //информационная часть

struct List *next; //указатель на следующий элемент списка

};

В приведенном примере информационная часть представляет собой одну целочисленную переменную (info), которая имеет тип int. Списки с элементами других типов описываются аналогично.

Пример. Список символов (‘a’, ’b’, ’c’), состоит из трех элементов. Первый элемент в этом списке – ‘a’, второй – ‘b’, третий – ‘c’. Представление этого списка стеком изображается на рис. 1, очередью – на рис. 2.

Рис.1 – Стек из трех элементов

Рис. 2 – Очередь из трех элементов

При этом в программе выражение pbeg означает указатель на первое звено в цепочке; * pbeg означает само первое звено, (* pbeg). info — первый элемент списка. По-другому первыйэлемент обозначается с помощью операции доступа к члену структуры через указатель: pbeg − > info. Выражение pbeg − > next означает указатель на второе звено. Далее,

*pbeg− > next — само второе звено,

pbeg− > next− > info — второй элемент списка,

pbeg− > next− > next — указатель на третье звено,

*pbeg–> next− > next — само третье звено,

pbeg− > next− > next− > info — третий элемент списка,

pbeg− > next− > next− > next — пустой указатель (конец списка).

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