Динамические структуры данных – список.

Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.

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

Основные отличия связного списка от стека и очереди следующие:

- для чтения доступен любой компонент списка;

- новые компоненты можно добавлять в любое место списка;

- при чтении компонент не удаляется из списка.

Из всего многообразия связанных списков можно выделить следующие основные:

• однонаправленные (односвязные) списки;
• двунаправленные (двусвязные) списки;
• циклические (кольцевые) списки.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

Над списками выполняются следующие операции:

- начальное формирование списка (запись первого компонента);

- добавление компонента в конец списка;

- чтение компонента с заданным ключом;

- вставка компонента в заданное место списка (обычно после компонента с заданным ключом);

- исключение компонента с заданным ключом из списка.

Для формирования списка и работы с ним необходимо иметь четыре переменные типа указатель, первая из которых определяет начало списка, остальные вспомогательные.