Списки и их разновидности
Связные списки и алгоритмы их обработки
В повседневной жизни под термином «список» (list) подразумевают некий перечень объектов реального мира, например, «список студентов группы» или «список комплектующих деталей на сладе». При этом указанный перечень может содержать не только наименование объектов, но и их дополнительные атрибуты. В нашем примере к таким атрибутам можно отнести пол студента, размер стипендии и т. д.
С точки зрения организации данных подсписком понимают структуруданных, представляющую собой логически связанную последовательность элементов. Элементом списка обычно является запись. Список называетсялинейным (linear list), если входящие в него элементы e1 , e2 ,…,en - линейно упорядочены. Упорядоченность элементов линейного списка может задаваться неявно путем последовательного расположения его элементов как в логической структуре, так и в памятиЭВМ. Такой список называют последовательным (sequential list).Примером последовательного списка является вектор, в котором элементы используются для хранения информации списка. С другой стороны, упорядоченность может задаваться с помощью специальных указателей (ссылок), располагаемых в элементах и дающих возможность для каждого элемента определить его непосредственныхпредшественника и последователя. Такой список называетсясвязным (linked) или цепным (chained) списком.
Связные списки относятся к классу динамических структур. Количество элементов в них заранее не фиксируется, оно зависит от потребностей решаемой в текущий момент задачи. Поскольку элемент связного списка может быть создан и уничтожен в любой момент времени, существование связного списка реализуется в куче.
Элемент связного списка называется обычно узлом (node) Каждый узел связного списка состоит из двух различных по назначению видов полей: содержательные (информационные) поля и поля структурных (или логических) указателей. В содержательных полях хранятся данные, ради которых и создавался список. Некоторые содержательные поля могут хранить указатели на данные, по каким либо причинам не вместившиеся в содержательные поля; такие указатели называются дополнительными или вторичными(secondary pointer). Поля логических или структурных указателей (logical pointer) хранят адреса других элементов списка. Пользуясь логическим указателем (адресом), можно получить доступ от элемента, содержащего этот указатель, к тому элементу списка, на который этот указатель направлен.
Определение связного списка отличается от определения массива, в котором следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.
В связном списке каждый узел является отдельным элементом. И, как правило, распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется слот памяти, а затем на этот слот устанавливается структурная ссылка от элемента списка. При удалении узла нужно всего лишь удалить ссылки, направленные на него от других элементов и освободить память, занимаемую его слотом.