Чтение онлайн

Структура

сама по себе бесполезна. Ее необходимо включать в другие структуры данных.

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

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

Для того чтобы создать и инициализировать связанный список, можно использовать следующее объявление.

Эта команда позволяет статически создать связанный список с именем

.

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

Для работы со связанными списками ядро предоставляет семейство функций. Все они принимают указатели на одну или более структур

. Все функции выполнены как функции с подстановкой тела (inline) на языке С, и их все можно найти в файле .

Интересно, что время выполнения всех этих функций масштабируется как O(1) [97] . Это значит, что они выполняются в течение постоянного интервала времени независимо от количества элементов списка, для которого они вызываются. Например, время добавления элемента в связанный список из 3 и 3000 элементов будет одинаковым. Это, возможно, и не вызывает удивления, но тем не менее, приятно.

Для добавления элемента в связанный список можно использовать следующую функцию.

Эта функция добавляет узел

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

Для добавления элемента в конец связанного списка служит следующая функция.

Эта функция добавляет новый элемент new в связанный список сразу перед элементом, на который указывает параметр

. Поскольку связанный список является кольцевым, то, как и в случае функции , в качестве параметра можно передавать указатель на любой элемент списка. Эту функцию можно использовать для реализации очереди, если передавать указатель на первый элемент.

Для удаления узла списка служит следующая функция.

Эта функция позволяет удалить из списка элемент, на который указывает параметр

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

Для удаления узла из списка и повторной инициализации этого узла служит следующая функция.

Эта. функция аналогична функции

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

Для перемещения узла из одного списка в другой предназначена следующая функция.

Эта функция удаляет элемент

из одного связанного списка и добавляет его в другой связанный список после элемента .

Для перемещения элемента из одного связанного списка в конец другого служит следующая функция.

Эта функция выполняет то же самое, что и функция

, но вставляет элемент перед элементом .

Для проверки того, пуст ли список, служит функция.

Эта функция возвращает ненулевое значение, если связанный список пуст, и нулевое значение в противном случае.

Для объединения двух не перекрывающихся связанных списков служит следующая функция.

Эта функция вставляет список, на который указывает параметр

, в другой список после параметра head.