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

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

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

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

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

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

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

Три основные операции над кольцевым связанным списком:

1. Вносимые
2. Удаление и
3. пересечение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, вставьте “VALUE2” после узла, содержащего “VALUE0”, предполагая, что начальной точкой является узел с “VALUE0”.

• Разорвите связь между первым и вторым узлами и поместите между ними узел с "VALUE2".
• Указатель next первого узла ведет к новому узлу, а указатель next нового узла ведет к тому, что ранее было вторым узлом.
• Остальная часть конфигурации остается без изменений. Все узлы переустановлены.tracспособные к самостоятельному выполнению задач.

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 1) Удалите циклическую тягу.

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

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

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

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

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

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

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

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

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

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

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

1. Нет необходимости в присвоении NULL в коде. Циклический список никогда не указывает на NULL-указатель, если он полностью не освобожден.
2. Циклические связанные списки выгодны для операций завершения списка, поскольку их начало и конец совпадают. Algorithms Например, алгоритм циклического планирования позволяет беспрепятственно перемещаться между процессами в очереди, не сталкиваясь с висячими или нулевыми указателями.
3. Циклический связанный список по-прежнему поддерживает все стандартные операции односвязного списка. двусвязный список Это даже позволяет избежать необходимости полного обхода списка для поиска элемента — в худшем случае, целевой элемент находится напротив начальной точки, поэтому нужно будет пройти максимум половину списка.

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

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

1. Циклические списки сложнее, чем односвязные списки.
2. RevПерестановка элементов в циклическом списке сложнее, чем перестановка элементов в односвязном или двусвязном списке.
3. Если завершение цикла не обрабатывается должным образом, код обхода может войти в бесконечный цикл.
4. Найти конец списка и правильно написать условия управления циклом сложнее.
5. Вставка в начало списка требует обхода всего списка до последнего узла (с точки зрения реализации).

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

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

#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. Существуют различные прототипы функций для:
   1. Добавление элемента в пустой связанный список
   2. Вставка в в настоящее время указано положение циклического связанного списка.
   3. Вставка после определенного индексированный значение в связанном списке.
   4. Удаление/Удаление после определенного индексированный значение в связанном списке.
   5. Удаление в текущей указанной позиции циклического связанного списка
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)

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

1. В коде функции addToEmpty выделите пустой узел, используя функцию malloc().
2. Поместите входящие данные во временный узел.
3. Назначьте временный узел последнему и установите его указатель next на самого себя, чтобы единственный узел указывал обратно на себя.
4. Верните последний указатель обратно в контекст функции 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;
…

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

1. Если список пуст, передайте управление функции addToEmpty() и верните управление.
2. Создайте временный узел, который будет размещен после текущего узла.
3. Соедините указатели, как показано на схеме выше.
4. Возвращает последний указатель, соответствующий шаблону, использованному в предыдущей функции.

...
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");
...

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

1. Если список пуст, игнорируйте ключ поиска, добавьте текущий элемент в качестве единственного узла в списке и верните управление.
2. В каждой итерации цикла do-while указатель previous хранит результат последнего пройденного цикла.
3. Только после этого происходит следующий этап обхода.
4. Цикл 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)
...

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

1. Если весь список был просмотрен, но элемент не найден, отобразите сообщение «Элемент не найден» и верните управление вызывающей стороне.
2. Если целевой узел найден, выделите новый узел для вставляемого значения.
3. Ссылка связать предыдущий узел с новым узлом и связать указатель next нового узла с переменной temp (переменной обхода).
4. Это помещает новый элемент непосредственно после целевого узла в циклическом связанном списке. Затем управление возвращается вызывающей стороне.

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)

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

1. Чтобы удалить последний (текущий) узел, сначала проверьте, пуст ли список. Если да, то удалить элемент невозможно.
2. Временная переменная продвигает звено на одну позицию вперед.
3. Свяжите последний указатель с узлом, следующим за первым узлом.
4. Освободите временный указатель, чтобы освободить память для несвязанного узла.

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");
...

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

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

    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;

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

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

...
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;
    }
}

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

1. Обход по списку узлов невозможен, если узлов нет — пользователь должен сначала выделить или вставить узел.
2. Если имеется только один узел, обход не требуется — содержимое узла выводится напрямую, и цикл while не выполняется.
3. Если узлов несколько, temp выводит каждый элемент вплоть до последнего.
4. В момент достижения последнего элемента цикл завершается, и функция возвращает управление функции main().

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

• Реализация циклического планирования в системных процессах и циклического планирования в высокоскоростной графике.
• Планирование по принципу «кольца токенов» в компьютерных сетях.
• Используется в дисплейных устройствах, таких как цифровые табло, требующие непрерывного отображения данных.

Часто задаваемые вопросы (FAQ)