Круговой связанный список: преимущества и недостатки

Что такое циклический связанный список?

Циклический связанный список — это последовательность узлов, организованная таким образом, что каждый узел можно проследить до самого себя. Здесь «узел» — это самоссылающийся элемент с указателями на один или два узла в непосредственной близости от него.

Ниже показано изображение циклического связанного списка с тремя узлами.

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

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

Базовый Operaв циклических связанных списках

Основные операции с циклическим связным списком:

Вносимые
Удаление и
пересечение

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

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

Вносимые Operaпроизводство

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

Дальше есть две возможности:

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

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

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

ПРИМЕЧАНИЕ. Указатель, который является мастером токена или началом/концом круга, можно изменить. Он все равно вернется к тому же узлу при обходе, о котором пойдет речь ниже.

Шаги в (a) i-iii показаны ниже:

(Существующий узел)

ШАГ 1) Разорвать существующую ссылку

ШАГ 2) Создайте прямую ссылку (от нового узла к существующему узлу)

ШАГ 3) Создайте циклическую ссылку на первый узел

Далее вы попытаетесь вставить после узла.

Например, вставим «VALUE2» после узла с «VALUE0». Предположим, что отправной точкой является узел с «VALUE0».

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

ПРИМЕЧАНИЕ. Поскольку существует циклическое расположение, вставка узла включает в себя одну и ту же процедуру для любого узла. Указатель, завершающий цикл, завершает цикл так же, как и любой другой узел.

Это показано ниже:

(Предположим, есть только два узла. Это тривиальный случай)

ШАГ 1) Удалить внутреннюю связь между подключенными узлами

ШАГ 2) Подключите левый узел к новому узлу.

ШАГ 3) Подключите новый узел к правому узлу.

удаление Operaпроизводство

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

Удаление текущего элемента
Удаление после элемента.

Удаление в начале/конце:

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

(Существующая установка)

ШАГ 1) Удалить круговую ссылку

ШАГИ 2) Удалить связь между первым и следующим, связать последний узел с узлом, следующим за первым.

ШАГ 3) Освободить/освободить первый узел

Удаление после узла:

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

ШАГ 1) Допустим, нам нужно удалить узел с «VALUE1».

ШАГ 2) Удалите связь между предыдущим узлом и текущим узлом. Свяжите его предыдущий узел со следующим узлом, на который указывает текущий узел (с помощью VALUE1).

ШАГ 3) Освободите или освободите текущий узел.

Обход циклического связанного списка

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

Преимущества кольцевого связанного списка

Некоторые из преимуществ циклических связанных списков:

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

Недостатки циклического связанного списка

Недостатки использования циклического связанного списка приведены ниже:

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

Односвязный список как циклический связанный список

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

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Расшифровка кода:

Первые две строки кода — это необходимые включаемые заголовочные файлы.
В следующем разделе описывается структура каждого самореферентного узла. Он содержит значение и указатель того же типа, что и структура.
Каждая структура неоднократно ссылается на объекты структуры того же типа.
Существуют различные прототипы функций для:
1. Добавление элемента в пустой связанный список
2. Вставка в в настоящее время указано положение циклического связанного списка.
3. Вставка после определенного индексированный значение в связанном списке.
4. Удаление/Удаление после определенного индексированный значение в связанном списке.
5. Удаление в текущей указанной позиции циклического связанного списка
Последняя функция печатает каждый элемент посредством кругового обхода в любом состоянии связанного списка.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
    
struct node *insertCurrent(struct node *last, int data)

Расшифровка кода:

Для кода addEmpty выделите пустой узел с помощью функции malloc.
Для этого узла поместите данные в переменную temp.
Назначьте и свяжите единственную переменную с временной переменной.
Верните последний элемент в контекст main()/приложения.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Объяснение кода

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

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );


    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Расшифровка кода:

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

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Расшифровка кода:

Если весь список пройден, но элемент не найден, отобразите сообщение «элемент не найден», а затем верните управление вызывающему объекту.
Если узел найден и/или узел еще не последний, создайте новый узел.
Ссылка предыдущий узел с новым узлом. Свяжите текущий узел с temp (переменной обхода).
Это гарантирует, что элемент будет помещен после определенного узла в циклическом связанном списке. Вернитесь к звонившему.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Объяснение кода

Чтобы удалить только последний (текущий) узел, проверьте, пуст ли этот список. Если да, то ни один элемент удалить невозможно.
Переменная temp просто перемещает одну ссылку вперед.
Свяжите последний указатель с указателем после первого.
Освободите указатель температуры. Он освобождает несвязанный последний указатель.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Объяснение кода

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

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Пояснение к программе

Если элемент найден после обхода всего связанного списка, отображается сообщение об ошибке, в котором говорится, что элемент не найден.
В противном случае элемент отделяется и освобождается на шагах 3 и 4.
Предыдущий указатель связан с адресом, указанным как «следующий» удаляемым элементом (temp).
Таким образом, указатель temp освобождается.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;    
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Объяснение кода

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

Применение кругового связанного списка

Реализация циклического планирования в системных процессах и циклического планирования в высокоскоростной графике.
Планирование Token Ring в компьютерных сетях.
Он используется в устройствах отображения, таких как доски объявлений, которые требуют непрерывного просмотра данных.

Что такое циклический связанный список?

Базовый Operaв циклических связанных списках

Вносимые Operaпроизводство

СТАТЬИ ПО ТЕМЕ

удаление Operaпроизводство

Обход циклического связанного списка

Преимущества кольцевого связанного списка

Недостатки циклического связанного списка

Односвязный список как циклический связанный список

Применение кругового связанного списка

Подпишитесь на рассылку