Структура данных «список».

Список – это упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения и исключения.

2. Ссылки.

Ссылка – это информация о связи данного компонента структуры с другими. В языке С наиболее удобно реализовать ссылки на основе использования указателей. Таким образом, компонент списка всегда состоит из двух частей:

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

3. Линейные списки – основные операции.

Список, отражающий отношение соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке; список нулевой длины называется пустым списком. Линейные списки являются простейшими динамическими структурами данных.

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

1. Создание списка.

Эта операция предполагает определение указателя начала списка и присвоение ему NULL-значения (т.е. никакого).

2. Перебор элементов списка.

Эта операция выполняется для линейных списков очень часто и состоит в последовательном доступе к элементам списка – ко всем до конца списка либо до нахождения искомого элемента. Для каждого из перебираемых элементов осуществляется некоторая обработка его информационной части: сравнение с образцом, печать, модификация и прочее.

3. Вставка элемента в список.

Вставка элемента в середину односвязного списка показана на рис.4., а в начало – на рис. 5.

Рис. 4. Вставка элемента в середину односвязного списка

Рис. 5. Вставка элемента в начало односвязного списка

4. Удаление элемента из списка.

Удаление элемента из списка показано на рис.6.

Рис. 6. Удаление элемента из односвязного списка

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

5. Перестановка элементов списка.

Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера на рис.7 приведена перестановка двух соседних элементов списка.

Рис. 7. Перестановка соседних элементов односвязного списка

Кроме указанных, можно придумать и другие операции. Но приведенные операции достаточно полно продемонстрировали основные принципы их реализации для односвязных списков.