В стеки или очереди компоненты можно добавлять только в какой либо один конец структуры данных, это относится и к извлечению компонент.
Связный (линейный) список является структурой данных, в произвольно выбранное место которого могут включаться данные, а также изыматься оттуда.
Каждая компонента списка определяется ключом. Обычно ключ либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.
Основные отличия связного списка от стека и очереди следующие:
- для чтения доступна любая компонента списка;
- новые компоненты можно добавлять в любое место списка;
- при чтении компонента не удаляется из списка.
Над списками выполняются следующие операции:
- начальное формирование списка (запись первой компоненты);
- добавление компоненты в конец списка;
- чтение компоненты с заданным ключом;
- вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);
- исключение компоненты с заданным ключом из списка.
Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая конец списка, остальныевспомогательные.
