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

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

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 — пустой указатель (конец списка).

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