Часто в программах надо использовать такие типы данных, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку заранее нельзя сказать, сколько памяти надо выделить - это выясняется только в процессе работы. Например, надо проанализировать текст и определить, сколько каких слов в нем встретилось, а также расставить их по алфавиту.
В таких случаях применяют данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент (узел) состоит из двух областей памяти:поля данных и ссылок
В простейшем случае каждый узел содержит всего одну ссылку. Для определенности будем считать, что решается задача частотного анализа текста - определения всех слов, встречающихся в тексте и их количества. В этом случае область данных элемента включает строку (длиной не более 40 символов) и целое число.
Каждый элемент содержит также ссылку на следующий за ним элемент. У последнего в списке элемента поле ссылки содержит NULL. Чтобы не потерять список, мы должны хранить адрес его первого узла – он называется "головой" списка. В программе надо объявить два новых типа данных - узел списка Node и указатель на него PNode. Узел представляет собой структуру, которая содержит три поля - строку, целое число и указатель на такой же узел.
Основными операциями являются добавление элемента в список и исключение из списка. Заметьте, что возможно два типа добавления - до и после заданного элемента.
