Структура данных циклического связного списка в C++

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

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

Схема, показанная ниже, предназначена для односвязного списка:

Схема односвязного списка

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

Такая схема представлена ниже:

Кольцевой связный список

Объявление

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

Для реализации циклического связного списка мы поддерживаем внешний указатель “last”, который указывает на последний узел в циклическом связном списке. Следовательно, last->next будет указывать на первый узел в связном списке.

Делая так, мы гарантируем, что при вставке нового узла в начале или в конце списка нам не нужно будет проходить весь список. Это связано с тем, что last указывает на последний узел, а last->next указывает на первый узел.

Это было бы невозможно, если бы мы указали внешний указатель на первый узел.

Основные операции

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

Вставка

Мы можем вставить узел в циклический связный список либо как первый узел (empty list — пустой список), в начале, в конце или между другими узлами. Давайте рассмотрим каждую из этих операций вставки, используя наглядное представление.

Читать также:  Строки в C++ с примерами

1) Вставка в пустой список

Вставка в пустой список

Когда в циклическом списке нет узлов, а список пуст, а последний указатель равен null, тогда мы вставляем новый узел N, указывая последний указатель на узел N, как показано выше. Следующий указатель N будет указывать на сам узел N, поскольку существует только один узел. Таким образом, N становится первым и последним узлом в списке.

2) Вставка в начало списка

Вставка в начало списка

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

N-> следующий = последний-> следующий

Последний-> следующий = N

3) Вставка в конец списка

Вставка в конец списка

Чтобы вставить новый узел в конец списка, выполните следующие действия:

N-> следующий = последний -> следующий;
последний -> следующий = N
последний = N

4) Вставка между списком

Вставка между списком

Предположим, нам нужно вставить новый узел N между N3 и N4, сначала нам нужно пройти по списку и найти узел, после которого должен быть вставлен новый узел, в данном случае его N3.

После того, как узел найден, мы выполняем следующие шаги:

N -> следующий = N3 -> Следующий;
N3 -> Следующий = N

Такая операция вставляет новый узел N после N3.

Удаление

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

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

Читать также:  Введение в алгоритмы поиска в C++

Графическое представление операции удаления показано ниже:

Графическое представление операции удаления

Обход

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

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

Теперь мы представим реализацию операций с циклическим связным списком с использованием C ++ и Java. Здесь мы реализовали операции вставки, удаления и обхода. Для ясного понимания мы изобразили циклический связанный список как

Операции вставки, удаления и обхода

Таким образом, к последнему узлу 50 мы снова присоединяем узел 10, который является первым узлом, тем самым указывая его как кольцевой связный список.

Программа на C++:

Вывод данных:

Созданный циклический связный список выглядит следующим образом:
10==>20==>30==>40==>50==>60==>10
Узел с данными 10 удаляется из списка
Кольцевой связный список после удаления 10 выглядит следующим образом:
20==>30==>40==>50==>60==>20

Программа на Java для операций с циклическим связным списком:

Вывод данных:

Созданный кольцевой связный список:
10==>20==>30==>40==>50==>60==>10
После удаления 40 кольцевой список будет:
10==>20==>30==>50==>60==>10

Преимущества и недостатки

Давайте обсудим некоторые преимущества и недостатки циклического связного списка:

Преимущества:

  • Мы можем перейти к любому узлу и перейти от любого узла. Нам просто нужно остановиться, когда мы снова посетим тот же узел.
  • Поскольку последний узел указывает на первый узел, переход к первому узлу от последнего узла занимает всего один шаг.

Недостатки:

  • Изменение кольцевого связного списка является сложным.
  • Поскольку узлы соединены, образуя кольцо (круг), нет надлежащей маркировки для начала или конца списка. Следовательно, трудно найти конец списка или элемент управления циклом. Если не позаботиться об этом, реализация может оказаться в бесконечном цикле.
  • Мы не можем вернуться к предыдущему узлу за один шаг. Мы должны сначала просмотреть весь список.

Читать также:  Рекурсия в С++

Применения циклического связного списка

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

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

Итог

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

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

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

В нашей следующей статье вы узнаете о структуре данных стека в С++.

С Уважением, МониторБанк

Добавить комментарий