Линейный список представляет собой последовательность n≥0 узлов Х[1], X[2], … , X[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре должно соблюдаться следующее условие: если n>0 и X[1] является первым узлом, а X[n] – последним, то k –й узел следует за X[k-1] и предшествует узлу X[k+1] для всех 1< k <n. Элемент списка состоит из двух частей: информационной, содержащей данные, и адресной, где хранятся указатели на следующие элементы.
В зависимости от количества полей в адресной части и порядка связывания элементов различают:
• Линейные односвязные списки – единственное адресное поле содержит адрес следующего элемента. Если следующий элемент отсутствует, то в адресное поле заносят константу nil;
• Линейные двусвязные списки – каждый элемент содержит адреса предыдущего и по-следующих элементов, соответственно, первый элемент в качестве адреса предыдущего, а последний – в качестве адреса следующего элемента содержит nil. Для описания элементов списка используют записи, например, элемент односвязного списка с двумя информационными и одним адресным полями может быть описан следующим образом:
Tape pe = ^element; {тип указателя}
element = record
name: string[16]; {информационное поле 1}
telefon: string[7]; {информационное поле 2}
p: pe; {адресное поле}
end;
Элемент двусвязного списка описывается с двумя адресными полями, например:
Tape pe = ^element; {тип указателя}
element = record
name: string[16]; {информационное поле 1}
telefon: string[7]; {информационное поле 2}
prev: pe; {адресное поле «предыдущий»}
next: pe; {адресное поле «следующий»}
end;
С линейными списками могут выполняться следующие операции:
1) Получение доступа к k-му узлу списка для проверки и/или изменения содержимого его полей.
2) Вставка нового узла сразу после или до k-го узла.
3) Удаление k-го узла.
4) Объединение в одном списке двух или более линейных списков.
5) Разбиение линейного списка на два или более списка.
6) Создание копии линейного списка.
7) Определение количества узлов в списке.
8) Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
9) Поиск узла с заданным значением в некотором поле.
В одном компьютерном приложении редко используются сразу все девять типов операций в общей их формулировке. Поэтому линейные списки могут иметь самые разные представления в зависимости от класса операций, которые наиболее часто должны с ними выполняться. Достаточно трудно создать единое представление линейных списков, при котором бы эффективно выполнялись все эти операции. Например, сравнительно сложно организовать доступ к k-му узлу длинного списка для произвольно выбранного k, если одновременно необходимо выполнять вставку и удаление элементов в середине списка. Поэтому различают разные типы линейных списков в зависимости от выполняемых с ними основных операций. Линейные списки, в которых операции вставки, удаления и доступа к значениям чаще всего выполняются в первом или последнем узле, получили следующие специальные названия.
Стек – это линейный список, все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка.
Очередь или односторонняя очередь - это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и ,как правило, операции доступа к данным) – на другом.
Дек или двусторонняя очередь - это линейный список, все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются на обоих концах списка.
Рис.1. Три наиболее важных класса линейных списков
Чаще других списков используют линейные односвязные списки, так как они сравнительно просты. Рассмотрим более подробно, как выполняются основные операции с такими списками.
