Программирование на языке высокого уровня. Марапулец Ю.В. - 63 стр.

      2.9.2. Линейные списки

      По своей встречаемости в типичных программах списки занимают второе место
после массивов. Многие языки программирования имеют встроенные типы списков, не-
которые (например, Lisp), даже построены на них. К сожалению в языке Си необходимо
конструировать их самостоятельно (в C++ работа со списками поддерживается стан-
дартными библиотеками, но и в этом случае необходимо знать их возможности и типич-
ные применения). Самый простой способ связать множество элементов - сделать так,
чтобы каждый элемент содержал ссылку на следующий. Такой список называется
«single-linked list» - однонаправленным (односвязным, цепным). Головой списка явля-
ется указатель на первый элемент, а конец помечен нулевым указателем. Ниже показан
пример списка, состоящего из четырех элементов (рис.2.4).




                                 Рис.2.4. Список из 4 элементов.

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

struct X{
        int Value;
        X *Next;
        X *Prev;
};



                                           63