Кръгов свързан списък: предимства и недостатъци

Какво е кръгов свързан списък?

Кръговият свързан списък е поредица от възли, подредени по такъв начин, че всеки възел може да бъде проследен до себе си. Тук „възел“ е самореферентен елемент с указатели към един или два възела в непосредствена близост до него.

По-долу е изображение на кръгъл свързан списък с 3 възела.

Тук можете да видите, че всеки възел може да бъде проследен до себе си. Примерът, показан по-горе, е кръгъл единично свързан списък.

Забележка: Най-простият кръгов свързан списък е възел, който проследява само себе си, както е показано

Basic Operaции в кръгови свързани списъци

Основните операции върху кръгъл свързан списък са:

1. вмъкване
2. Изтриване и
3. Обход

• Вмъкването е процес на поставяне на възел на определена позиция в кръговия свързан списък.
• Изтриването е процес на премахване на съществуващ възел от свързания списък. Възелът може да бъде идентифициран чрез появата на неговата стойност или чрез неговата позиция.
• Обхождането на кръгов свързан списък е процес на показване на съдържанието на целия свързан списък и обратно проследяване до изходния възел.

В следващия раздел ще разберете вмъкването на възел и възможните видове вмъкване в кръгов единично свързан списък.

вмъкване OperaАЦИ

Първоначално трябва да създадете един възел, който сочи към себе си, както е показано на това изображение. Без този възел вмъкването създава първия възел.

След това има две възможности:

• Вмъкване в текущата позиция на кръговия свързан списък. Това съответства на вмъкване в началото на края на редовен единичен свързан списък. В кръгъл свързан списък началото и краят са еднакви.
• Вмъкване след индексиран възел. Възелът трябва да бъде идентифициран чрез номер на индекс, съответстващ на стойността на неговия елемент.

За вмъкване в началото/края на кръговия свързан списък, което е на позицията, където е добавен първият по рода си възел,

• Ще трябва да прекъснете съществуващата самовръзка към съществуващия възел
• Следващият указател на новия възел ще се свърже към съществуващия възел.
• Следващият указател на последния възел ще сочи към вмъкнатия възел.

ЗАБЕЛЕЖКА: Показалецът, който е главният символ или началото/краят на кръга, може да бъде променен. Той все пак ще се върне към същия възел при обхождане, обсъдено по-напред.

Стъпките в (a) i-iii са показани по-долу:

(Съществуващ възел)

ЕТАП 1) Прекъснете съществуващата връзка

ЕТАП 2) Създайте препращаща връзка (от нов възел към съществуващ възел)

ЕТАП 3) Създайте връзка към първия възел

След това ще опитате вмъкване след възел.

Например, нека вмъкнем „VALUE2“ след възела с „VALUE0“. Да приемем, че началната точка е възелът с „VALUE0“.

• Ще трябва да прекъснете линията между първия и втория възел и да поставите възела с „VALUE2“ между тях.
• Следващият указател на първия възел трябва да се свързва с този възел, а следващият указател на този възел трябва да се свързва с предишния втори възел.
• Останалата част от подредбата остава непроменена. Всички възли са проследими до себе си.

ЗАБЕЛЕЖКА: Тъй като има циклично подреждане, вмъкването на възел включва същата процедура за всеки възел. Указателят, който завършва цикъл, завършва цикъла точно както всеки друг възел.

Това е показано по-долу:

(Да кажем, че има само два възела. Това е тривиален случай)

ЕТАП 1) Премахнете вътрешната връзка между свързаните възли

ЕТАП 2) Свържете възела от лявата страна към новия възел

ЕТАП 3) Свържете новия възел към възела от дясната страна.

заличаване OperaАЦИ

Нека приемем кръгъл свързан списък с 3 възела. Случаите за изтриване са дадени по-долу:

• Изтриване на текущия елемент
• Изтриване след елемент.

Изтриване в началото/края:

1. Преминете към първия възел от последния възел.
2. За да изтриете от края, трябва да има само една стъпка на преминаване, от последния възел до първия възел.
3. Изтрийте връзката между последния възел и следващия възел.
4. Свържете последния възел със следващия елемент на първия възел.
5. Освободете първия възел.

(Съществуваща настройка)

СТЪПКА 1) Премахнете кръговата връзка

СТЪПКИ 2) Премахнете връзката между първия и следващия, свържете последния възел към възела, следващ първия

ЕТАП 3) Освободете/освободете първия възел

Изтриване след възел:

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

ЕТАП 1) Да кажем, че трябва да изтрием възел с „VALUE1“.

ЕТАП 2) Премахнете връзката между предишния възел и текущия възел. Свържете неговия предишен възел със следващия възел, посочен от текущия възел (със VALUE1).

ЕТАП 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. Временната променлива просто преминава една връзка напред.
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 в компютърни мрежи.
• Използва се в дисплейни единици като табла за магазини, които изискват непрекъснато преминаване на данни.