Круговий пов’язаний список: переваги та недоліки

Що таке циклічний пов’язаний список?

Круговий пов’язаний список — це послідовність вузлів, упорядкованих таким чином, що кожен вузол можна відстежити до самого себе. Тут «вузол» — це самопосилальний елемент із покажчиками на один або два вузли в безпосередній близькості.

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

Круговий зв’язаний список

Тут ви бачите, що кожен вузол можна відстежити до самого себе. Наведений вище приклад є кільцевим однозв’язаним списком.

Примітка. Найпростіший циклічний пов’язаний список — це вузол, який відстежує лише сам себе, як показано

Круговий зв’язаний список

Базовий Operaу кругових пов’язаних списках

Основні операції над циклічним пов’язаним списком:

  1. вставка
  2. Видалення і
  3. Обхід
  • Вставка — це процес розміщення вузла у вказаній позиції в циклічному зв’язаному списку.
  • Видалення — це процес видалення існуючого вузла зі зв’язаного списку. Вузол можна ідентифікувати за його значенням або за його положенням.
  • Обхід циклічного пов’язаного списку — це процес відображення всього вмісту зв’язаного списку та повернення назад до вихідного вузла.

У наступному розділі ви зрозумієте вставку вузла та типи вставки, можливі в кільцевому однозв’язаному списку.

вставка Operaції

Спочатку вам потрібно створити один вузол, який вказує на себе, як показано на цьому зображенні. Без цього вузла вставка створює перший вузол.

вставка Operaції

Далі є дві можливості:

  • Вставка в поточну позицію циклічного пов’язаного списку. Це відповідає вставці на початку кінця звичайного єдиного пов’язаного списку. У кільцевому пов’язаному списку початок і кінець однакові.
  • Вставка після індексованого вузла. Вузол має бути ідентифікований номером індексу, що відповідає значенню його елемента.

Для вставки на початку/кінці циклічного пов’язаного списку, тобто в позиції, де було додано перший вузол,

  • Вам доведеться розірвати існуюче власне посилання на існуючий вузол
  • Наступний покажчик нового вузла посилатиметься на існуючий вузол.
  • Наступний покажчик останнього вузла вказуватиме на вставлений вузол.

ПРИМІТКА. Покажчик, який є головним маркером, або початок/кінець кола можна змінити. Він все одно повертатиметься до того самого вузла під час обходу, який обговорювався вище.

Етапи (a) i-iii показані нижче:

вставка Operaції

(Існуючий вузол)

вставка Operaції

КРОК 1) Розірвати існуюче посилання

вставка Operaції

КРОК 2) Створення прямого посилання (від нового вузла до існуючого вузла)

вставка Operaції

КРОК 3) Створіть зв'язок циклу з першим вузлом

Далі ви спробуєте вставити після вузла.

Наприклад, вставимо «VALUE2» після вузла з «VALUE0». Припустимо, що початковою точкою є вузол із «VALUE0».

  • Вам потрібно буде розірвати лінію між першим і другим вузлом і розмістити вузол із «VALUE2» між ними.
  • Наступний покажчик першого вузла має посилатися на цей вузол, а наступний покажчик цього вузла має посилатися на попередній другий вузол.
  • Решта домовленості залишається без змін. Усі вузли відстежуються до самих себе.

ПРИМІТКА. Оскільки існує циклічне розташування, вставлення вузла передбачає однакову процедуру для будь-якого вузла. Покажчик, який завершує цикл, завершує цикл, як і будь-який інший вузол.

Це показано нижче:

вставка Operaції

(Припустимо, є лише два вузли. Це тривіальний випадок)

вставка Operaції

КРОК 1) Видаліть внутрішню зв'язок між підключеними вузлами

вставка Operaції

КРОК 2) З’єднайте вузол лівої сторони з новим вузлом

вставка Operaції

КРОК 3) Підключіть новий вузол до правого вузла.

видалення Operaції

Припустимо циклічний пов’язаний список із 3 вузлами. Нижче наведено випадки видалення:

  • Видалення поточного елемента
  • Видалення після елемента.

Видалення на початку/кінці:

  1. Перейдіть до першого вузла від останнього вузла.
  2. Щоб видалити з кінця, має бути лише один крок обходу, від останнього вузла до першого вузла.
  3. Видалити зв’язок між останнім вузлом і наступним вузлом.
  4. Зв’яжіть останній вузол з наступним елементом першого вузла.
  5. Звільніть перший вузол.

видалення Operaції

(Існуюче налаштування)

видалення Operaції

КРОК 1) Видалити кругове посилання

видалення Operaції

КРОК 2) Видаліть зв’язок між першим і наступним, пов’яжіть останній вузол із вузлом, наступним за першим

видалення Operaції

КРОК 3) Звільнити/звільнити перший вузол

Видалення після вузла:

  1. Перейдіть до наступного вузла, який буде видалено.
  2. Перейдіть до наступного вузла, навівши покажчик на попередній вузол.
  3. З’єднайте попередній вузол із вузлом після поточного вузла, використовуючи його наступний покажчик.
  4. Звільніть поточний (від’єднаний) вузол.

видалення Operaції

КРОК 1) Скажімо, нам потрібно видалити вузол із «VALUE1».

видалення Operaції

КРОК 2) Видаліть зв’язок між попереднім і поточним вузлом. Пов’яжіть його попередній вузол із наступним вузлом, на який вказує поточний вузол (зі значенням VALUE1).

видалення Operaції

КРОК 3) Звільнити або відмінити поточний вузол.

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

Щоб пройти круговий пов’язаний список, починаючи з останнього вказівника, перевірте, чи сам останній вказівник має значення NULL. Якщо ця умова хибна, перевірте, чи є лише один елемент. В іншому випадку переміщайтеся за допомогою тимчасового вказівника, доки останній вказівник не буде знову досягнутий або стільки разів, скільки потрібно, як показано на GIF нижче.

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

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

Деякі з переваг циклічних пов’язаних списків:

  1. Немає вимог щодо призначення NULL у коді. Циркулярний список ніколи не вказує на покажчик NULL, якщо він не повністю звільнений.
  2. Циркулярні пов'язані списки вигідні для кінцевих операцій, оскільки початок і кінець збігаються. Algorithms наприклад, планування Round Robin, може акуратно усунути процеси, які стоять у черзі циклічним способом, не зустрічаючи висячих або NULL-посилальних покажчиків.
  3. Циркулярний пов’язаний список також виконує всі регулярні функції однозв’язаного списку. По суті, круговий двозв'язані списки обговорене нижче може навіть усунути потребу в обході повної довжини, щоб знайти елемент. Цей елемент був би лише навпроти початку, завершуючи лише половину пов’язаного списку.

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

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

  1. Циркулярні списки складні порівняно з однозв'язані списки.
  2. RevІнший циклічний список є складним у порівнянні з одиночними або подвійними списками.
  3. Якщо поводитися необережно, код може зациклюватися.
  4. Важче знайти кінець списку та керування циклом.
  5. Вставляючи на початку, ми повинні пройти весь список, щоб знайти останній вузол. (Перспектива впровадження)

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

Рекомендуємо спробувати прочитати та реалізувати наведений нижче код. Він представляє арифметику покажчика, пов’язану з циклічними пов’язаними списками.

#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. Для коду addEmpty виділіть порожній вузол за допомогою функції malloc.
  2. Для цього вузла розмістіть дані у змінній temp.
  3. Призначте та зв’яжіть єдину змінну з тимчасовою змінною
  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. Якщо немає жодного елемента для вставки, ви повинні переконатися, що ви додали до порожнього списку та повернули керування.
  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 переконайтеся, що існує попередній покажчик, який містить останній пройдений результат.
  3. Тільки після цього може відбутися наступний обхід.
  4. Якщо дані знайдено або temp повертається до останнього вказівника, функція do-while завершується. Наступний розділ коду визначає, що робити з елементом.
...
    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. посилання попередній вузол з новим вузлом. Пов’яжіть поточний вузол із 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. Змінна temp просто перетинає одне посилання вперед.
  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. Процес триває, доки не буде знайдено елемент, або доки наступний елемент не повернеться до останнього покажчика.
    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. Попередній вказівник пов’язаний з адресою, на яку вказує елемент, який потрібно видалити (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. У момент досягнення останнього елемента цикл завершується, і функція повертає виклик головної функції.

Застосування Циркулярного пов’язаного списку

  • Реалізація циклічного планування в системних процесах і циклічного планування у високошвидкісній графіці.
  • Планування Token Ring в комп'ютерних мережах.
  • Він використовується в блоках відображення, таких як дошки магазинів, які потребують постійного обходу даних.