Связные списки. 
Связные списки

Список представляет собой позиционно-ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Элемент списка хранит значение объекта, включённого в список. Номера элементов в списке задаются в линейном порядке, начиная со значения 0 или 1. У списка есть первый и последний элементы. У всех остальных элементов есть единственный предшествующий элемент и последующий элемент. Идея связных списков состоит в представлении данных в виде объектов, связанных друг с другом указателями.

S1 и S2 являются указателями начала двух разных односвязных списков, в которые одновременно входит каждый из пяти элементов, а P1 и P2 — обозначения связок в 1 и 2 односвязных списках соответственно. S1 и S2 являются компонентами двух разных дескрипторов односвязных списков. (Рисунок 1).

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

Ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла невозможно.

Двусвязный список может и не быть линейным, если второй указатель каждого элемента списка задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому первым указателем. Каждый элемент такого двухсвязного списка содержится в двух разных односвязных списках, как показано на рисунке 1:

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

Многосвязные списки представляют собой динамические структуры данных, в основу которых положены 1- или 2-связные списка, в которых имеются дополнительные связи между звеньями. Чаще всего, такие связи проводятся между далеко отстоящими звеньями, например, обозначающими категории данных. По способу организации связей с писки могут быть: линейными.

Линейный односвязный список является самым простым видом связных списков, к которому относятся односвязные и двусвязные списки.

Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.

Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант — ветвящийся список, фактически являющийся одной из древовидных структур данных.

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

добавление нового звена списка (вставка звена); удаление звена; просмотр (или прохождение) списка; поиск данных в списке; создание ведущего (заглавного) звена (при необходимости); сортировка списка; обращение (реверсирование) списка, т. е. перестановка всех его звеньев в обратном порядке. список программирование драйвер связный Реализация операций над связными списками Перебор элементов списка. Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка — ко всем до конца списка или до нахождения искомого элемента.

• 1) Указатель текущего элемента устанавливается на начало списка.
• 2) Если указатель текущего элемента пустой — конец перебора.
• 3) Обрабатывается информационная часть текущего элемента, на который из текущего элемента выбирается указатель на следующий элемент, следующий элемент становится текущим.

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

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