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

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

Определение 3.2 Связный список - это набор элементов, причем каждый из них является частью узла (node), который также содержит ссылку (link) на узел.

Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочыми (self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические (cyclic) структуры. Последствия этих двух фактов станут ясны при рассмотрении конкретных представлений и применений связных списков.

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

Это пустая (null) ссылка, не указывающая на какой-либо узел.

Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.

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

В каждом случае отслеживание ссылок от первого узла до последнего формирует последовательное расположение элементов. Массивы также задают последовательное расположение элементов, но оно реализуется косвенно, за счет позиции в массиве. (Массивы также поддерживают произвольный доступ по индексу, что невозможно для списков.)

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

Связные списки являются примитивными конструкциями в некоторых языках программирования, но не в С++. Однако базовые строительные блоки, о которых шла речь в разделе 3.1, хорошо приспособлены для реализации связных списков. Указатели для ссылок и структуры для узлов описываются следующим образом:

Btruct node { Item item; node *next; }; typedef node *link;

Эта пара выражений представляет собой не более чем код С++ для определения 3.2. Узлы состоят из элементов (указанного здесь типа Item) и указателей на узлы. Указатели на узлы также называются ссылками. Более сложные случаи будут представлены в главе 4. Они обеспечивают большую гибкость и более эффективную реализацию определенных операций, но этот простой пример достаточен для понимания основ обработки списков. Подобные соглашения для связных структур используются на протяжении всей книги.

Распределение памяти имеет ключевое значение для эффективного использования связных списков. Выше описана единственная структура (struct node), но будет получено множество экземпляров этой структуры, по одному для каждого узла, который придется использовать. Как только возникает необходимость использовать новый узел, для него следует зарезервировать память. При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервированием памяти во время выполнения, посредством вызовов системных операторов управления памятью. Например, в строке кода

link X = new node;

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

В языке С++ широко принято инициализировать область хранения, а не только выделять для нее память. В связи с этим обычно каждую описываемую структуру включается конструктор (constructor). Конструктор представляет собой функцию, которая описывается внутри структуры и имеет такое же имя. Конструкторы подробно обсуждаются в главе 4. Они предназначены для предоставления исходных значений данным структуры. Для этого конструкторы автоматически вызываются при создании экземпляра структуры. Например, если описать узел списка при помощи следующего кода:

struct node { Item item; node *next; node (Item x; node *t) { item = x; next = t; };

typedef node *link;

TO оператор

link t = new node(x, t) ;

не только резервирует достаточный для узла объем памяти и возвращает указатель на него в переменной t, но и присваивает полю item узла значение х, а указателю поля - значение t. Конструкторы помогают избегать ошибок, связанных с инициализацией данных.

Теперь, когда узел списка создан, возникает задача осуществления ссылок на заключаемую в нем информацию - элемент и ссылку. Мы уже ознакомились с базовыми операциями, необходимыми для выполнения этой задачи: достаточно снять косвенность указателя, а затем использовать имена членов структуры. Ссылка х на элемент узла (тип Item) имеет вид (*x).item, а на ссылку (тип link) - (*x).link. Эти операции так часто используются, что в языке С++ для них существуют сокращенные эквиваленты: x->item и x->link. Кроме того, часто возникает необходимость в выражении: узел, указываемый ссылкой х , поэтому упростим его: узел х . Ссылка служит именем узла.

Соответствие между ссылками и указателями С++ имеет большое значение, но следует учитывать, что ссылки являются абстракцией, а указатели - конкретным представлением. Можно разрабатывать алгоритмы, где используются узлы и ссылки, а также выбрать одну из многочисленных реализаций этой идеи. Например, ссылки можно представлять с индексами, что будет показано в конце раздела.

Рисунки 3.3 и 3.4 иллюстрируют две основные операции, выполняемые со связными списками. Можно удалить любой элемент связного списка, уменьшив его длину на 1; а также вставить элемент в любую позицию списка путем увеличения длины на 1. В этих рисунках для простоты предполагается, что списки циклические и никогда не становятся пустыми. В разделе 3.4 рассматриваются null-ссылки, фиктивные узлы и пустые списки. Как показано на рисунках, для вставки или удаления необходимо лишь два оператора С++. Для удаления узла, следующего после узла X, используются такие операторы:

t = x->next; x->next = t->next; или проще:

x->next = x->next; x->next = t;

Для вставки в список узла t в позицию, следующую за узлом X используется такие операторы:

t->next = x->next; x->next = t;

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

Связные списки плохо приспособлены для поиска к-того элемента (по индексу) - операции, которая характеризует эффективность доступа к данным массивов. В массиве для доступа к А:-тому элементу используется простая запись а[к], а в списке для этого необходимо отследить к ссылок.

РИСУНОК 3.3 УДАЛЕНИЕ В СВЯЗНОМ СПИСКЕ

Для удаления из связного списка узла, следующего за узлом х, значение t устанавливается таким образом, чтобы указатель ссылался на удаляемый узел, а затем изменяется указательх: t->next. Указатель t может использоваться для ссылки на удаляемый узел. Хотя его ссылка по-прежнему указывает на список, обычно подобная ссылка не используется после удаления узла из списка, за исключением, возможно, информирования системы через оператор delete о том, что задействованная память может быть вновь востребована.