ЛИНЕЙНЫЕ СПИСКИ

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

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

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

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

• для чтения доступна любая компонента списка;
• новые компоненты можно добавлять в любое место списка;
• при чтении компонента не удаляется из списка.

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

• начальное формирование списка (запись первой компоненты);
• добавление компоненты в конец списка;
• чтение компоненты с заданным ключом;
• вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);
• исключение компоненты с заданным ключом из списка.

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