Линейные списки. Общее понятие

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

Такой список называется однонаправленным (односвязным).

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

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

Каждый элемент списка содержит ключ, идентифицирующий этот элемент.

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

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

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

Ключи разных элементов списка могут совпадать.

Над списками можно выполнять следующие операции:
• начальное формирование списка (создание первого элемента);
• добавление элемента в конец списка;
• чтение элемента с заданным ключом;
• вставка элемента в заданное место списка (до или после элемента с заданным ключом);
• удаление элемента с заданным ключом;
• упорядочивание списка по ключу.