Okrągła lista połączona: zalety i wady

Co to jest cykliczna lista połączona?

Lista powiązana cykliczna to sekwencja węzłów ułożonych w taki sposób, że każdy węzeł można ponownietracdo samego siebie. Każdy „węzeł” jest elementem samoodnoszącym się, posiadającym wskaźniki do jednego lub dwóch węzłów w swoim bezpośrednim sąsiedztwie.

Poniżej znajduje się ilustracja okrągłej listy połączonej z 3 węzłami.

Tutaj widać, że każdy węzeł jest ponownietraczdolny do samodzielnego działania. Przykład pokazany powyżej to cykliczna lista jednokierunkowa.

Uwaga: najprostsza lista powiązana kołowa to pojedynczy węzeł, którego następny wskaźnik tracwraca do siebie, jak pokazano poniżej.

Basic Operacje w listach powiązanych cyklicznie

Trzy podstawowe operacje na liście cyklicznej to:

1. Wprowadzenie
2. Usunięcie i
3. Przemierzanie

• Wstawianie to proces umieszczania węzła w określonej pozycji na liście połączonej cyklicznie.
• Usuwanie to proces usuwania istniejącego węzła z połączonej listy. Węzeł można zidentyfikować po wystąpieniu jego wartości lub po jego położeniu.
• Przeglądanie listy powiązanej cyklicznie to proces wyświetlania całej zawartości listy powiązanej i ponownegotracpowrót do węzła źródłowego.

W następnej sekcji wyjaśniono, jak działa wstawianie i jakie dwa typy wstawiania są możliwe w cyklicznej liście jednokierunkowej.

Wprowadzenie Operacja

Najpierw tworzysz jeden węzeł, którego kolejny wskaźnik wskazuje na niego samego, jak pokazano poniżej. Bez tego węzła początkowego, pierwsze wstawienie staje się pierwszym węzłem na liście.

Dalej są dwie możliwości:

• Wstawianie w bieżącej pozycji listy okrężnej. Odpowiada to wstawianiu na początku lub na końcu zwykłej listy jednokierunkowej — w liście okrężnej początek i koniec znajdują się w tym samym punkcie.
• Wstawienie po indeksowanym węźle. Węzeł powinien być identyfikowany poprzez numer indeksu odpowiadający wartości jego elementu.

Aby wstawić na początku lub na końcu listy powiązanej kołowo — czyli w miejscu, w którym dodano pierwszy węzeł — wykonaj poniższe kroki:

• Będziesz musiał przerwać istniejące połączenie własne z istniejącym węzłem
• Następny wskaźnik nowego węzła będzie połączony z istniejącym węzłem.
• Następny wskaźnik ostatniego węzła będzie wskazywał wstawiony węzeł.

UWAGA: Wskaźnik oznaczający początek lub koniec okręgu można przypisać do dowolnego węzła. Przejście nadal będzie prowadzić do tego samego węzła, co zostanie omówione w dalszej części artykułu.

Kroki z (a) i-iii pokazano poniżej:

(Istniejący węzeł)

Krok 1) Przerwij istniejące łącze

Krok 2) Utwórz łącze do przodu (z nowego węzła do istniejącego węzła)

Krok 3) Utwórz pętlę do pierwszego węzła

Następnie spróbujesz wstawić po węźle.

Na przykład wstaw „WARTOŚĆ2” po węźle zawierającym „WARTOŚĆ0”, zakładając, że punktem początkowym jest węzeł zawierający „WARTOŚĆ0”.

• Przerwij połączenie między pierwszym i drugim węzłem i umieść pomiędzy nimi węzeł z „VALUE2”.
• Następny wskaźnik pierwszego węzła łączy się z nowym węzłem, a następny wskaźnik nowego węzła łączy się z tym, co poprzednio było drugim węzłem.
• Reszta układu pozostaje bez zmian. Wszystkie węzły są ponownietraczdolnych do samorozwoju.

UWAGA: Ponieważ układ jest cykliczny, procedura wstawiania węzła jest identyczna niezależnie od wybranej pozycji. Wskaźnik zamykający cykl zachowuje się jak każdy inny wskaźnik na liście.

Pokazano to poniżej:

(Powiedzmy, że są tylko dwa węzły. To trywialny przypadek)

Krok 1) Usuń wewnętrzne połączenie między połączonymi węzłami

Krok 2) Połącz węzeł po lewej stronie z nowym węzłem

Krok 3) Połącz nowy węzeł z węzłem po prawej stronie.

usunięcie Operacja

Załóżmy, że mamy 3-węzłową listę cykliczną. Dwa przypadki usunięcia to:

• Usuwanie bieżącego elementu
• Usunięcie po elemencie.

Skreślenie na początku/końcu:

1. Przejdź do pierwszego węzła z ostatniego węzła.
2. Usuwanie od końca wymaga tylko jednego kroku przejścia, od ostatniego węzła do pierwszego węzła.
3. Usuń połączenie pomiędzy ostatnim i pierwszym węzłem.
4. Połącz ostatni węzeł z kolejnym elementem pierwszego węzła.
5. Uwolnij pierwszy węzeł.

(Istniejąca konfiguracja)

Krok 1) Usuń łącze kołowe

Krok 2) Usuń połączenie między pierwszym a kolejnym węzłem, połącz ostatni węzeł z węzłem następującym po pierwszym

Krok 3) Zwolnij/zwolnij pierwszy węzeł

Usuwanie po węźle:

1. Przechodź, aż następny węzeł będzie węzłem przeznaczonym do usunięcia.
2. Przejdź do następnego węzła, umieszczając wskaźnik na poprzednim węźle.
3. Połącz poprzedni węzeł z węzłem następującym po bieżącym węźle, używając jego następnego wskaźnika.
4. Uwolnij bieżący (odłączony) węzeł.

Krok 1) Załóżmy, że musimy usunąć węzeł z „VALUE1”.

Krok 2) Usuń połączenie pomiędzy poprzednim węzłem i bieżącym węzłem, a następnie połącz poprzedni węzeł bezpośrednio z węzłem wskazywanym przez następny wskaźnik bieżącego węzła (węzeł po VALUE1).

Krok 3) Uwolnij lub zwolnij bieżący węzeł.

Przechodzenie przez cykliczną listę połączoną

Aby przejść przez listę cykliczną od ostatniego wskaźnika, najpierw sprawdź, czy ostatni wskaźnik ma wartość NULL. Jeśli nie, sprawdź, czy lista ma tylko jeden element. W przeciwnym razie przejdź przez listę z tymczasowym wskaźnikiem, aż ponownie dotrzesz do ostatniego wskaźnika, jak pokazano na poniższej animacji.

Zalety cyklicznej listy połączonej

Oto niektóre zalety list połączonych cyklicznie:

1. Brak wymogu przypisania wartości NULL w kodzie. Lista cykliczna nigdy nie wskazuje na wskaźnik NULL, chyba że całkowicie zwolniono przydział.
2. Listy cykliczne są korzystne w przypadku operacji na końcu listy, ponieważ początek i koniec pokrywają się. Algorithms takie jak harmonogramowanie typu round-robin pozwala na czyste przechodzenie przez procesy w kolejce, bez napotykania wiszących lub pustych wskaźników.
3. Lista powiązana cykliczna nadal obsługuje wszystkie standardowe operacje listy jednokierunkowej. Lista powiązana cykliczna lista dwukierunkowo powiązana może nawet wyeliminować konieczność przechodzenia całej listy w celu jej zlokalizowania — w najgorszym przypadku element docelowy znajduje się naprzeciwko wskaźnika początkowego, więc konieczne jest przejście co najwyżej połowy listy.

Wady cyklicznej listy połączonej

Poniżej przedstawiono wady korzystania z cyklicznej listy połączonej:

1. Listy kołowe są bardziej złożone niż listy pojedynczo połączone.
2. Revodwracanie listy cyklicznej jest bardziej skomplikowane niż odwracanie listy jedno- lub dwukierunkowo powiązanej.
3. Jeśli zakończenie pętli nie zostanie obsłużone ostrożnie, kod przechodzenia może wejść w pętlę nieskończoną.
4. Trudniej jest znaleźć koniec listy i zapisać prawidłowe warunki sterowania pętlą.
5. Wstawienie na początku wymaga przejścia przez całą listę, aby dotrzeć do ostatniego węzła (z perspektywy implementacji).

Lista pojedynczo połączona jako lista połączona cyklicznie

Zachęcamy do przeczytania i zaimplementowania poniższego kodu w języku C. Ilustruje on arytmetykę wskaźników związaną z cykliczną listą jednokierunkową.

#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()
{
...

Wyjaśnienie kodu:

1. Pierwsze dwie linie kodu to niezbędne pliki nagłówkowe.
2. W następnej sekcji zdefiniowano strukturę każdego węzła samoodniesieniowego. Zawiera on wartość i wskaźnik tego samego typu co struktura.
3. Każda instancja struktury jest powiązana z innymi obiektami struktury tego samego typu.
4. Istnieją różne prototypy funkcji dla:
   1. Dodawanie elementu do pustej listy połączonej
   2. Wstawianie na obecnie wskazany pozycja okrągłej listy połączonej.
   3. Wstawianie po konkretnym zindeksowane wartość na połączonej liście.
   4. Usuwanie/Usuwanie po konkretnym zindeksowane wartość na połączonej liście.
   5. Usuwanie w aktualnie wskazanej pozycji listy połączonej cyklicznie
5. Ostatnia funkcja drukuje każdy element poprzez przechodzenie cykliczne w dowolnym stanie połączonej listy.

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)

Wyjaśnienie kodu:

1. W kodzie addToEmpty przydziel pusty węzeł za pomocą funkcji malloc().
2. Umieść dane przychodzące w węźle tymczasowym.
3. Przypisz węzeł tymczasowy do ostatniego i ustaw jego następny wskaźnik na siebie, tak aby pojedynczy węzeł wskazywał z powrotem na siebie.
4. Zwróć ostatni wskaźnik do kontekstu main() / aplikacji.

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;
…

Wyjaśnienie kodu

1. Jeżeli lista jest pusta, przekaż sterowanie do addToEmpty() i zwróć je.
2. Utwórz tymczasowy węzeł, który zostanie umieszczony za bieżącym węzłem.
3. Połącz wskaźniki tak jak pokazano na powyższym schemacie.
4. Zwróć ostatni wskaźnik, pasujący do wzorca użytego w poprzedniej funkcji.

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

Wyjaśnienie kodu:

1. Jeżeli lista jest pusta, zignoruj ​​klucz wyszukiwania, dodaj bieżący element jako jedyny węzeł na liście i zwróć sterowanie.
2. W każdej iteracji pętli do-while poprzedni wskaźnik przechowuje wynik ostatnio przebytej pętli.
3. Dopiero wtedy następuje kolejny krok przechodzenia.
4. Operacja „do-while” kończy się, gdy dane docelowe zostaną znalezione lub gdy zmienna temp ponownie osiągnie ostatni wskaźnik. Poniższy blok kodu decyduje, co zrobić ze znalezionym elementem.

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

Wyjaśnienie kodu:

1. Jeśli cała lista została przeszukana, ale element nie został znaleziony, wyświetl komunikat „Element nie został znaleziony” i zwróć sterowanie do wywołującego.
2. Jeśli węzeł docelowy zostanie znaleziony, przydziel nowy węzeł dla wartości do wstawienia.
3. Połączyć poprzedni węzeł do nowego węzła i połącz następny wskaźnik nowego węzła ze zmienną temp (zmienną przeglądania).
4. Umieszcza to nowy element bezpośrednio za węzłem docelowym na liście cyklicznej. Sterowanie wraca do wywołującego.

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)

Wyjaśnienie kodu

1. Aby usunąć ostatni (bieżący) węzeł, najpierw sprawdź, czy lista jest pusta. Jeśli tak, nie można usunąć żadnego elementu.
2. Zmienna temp przesuwa się o jedno łącze do przodu.
3. Połącz ostatni wskaźnik z węzłem znajdującym się za pierwszym węzłem.
4. Zwolnij wskaźnik tymczasowy, aby zwolnić niepowiązany węzeł.

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

Wyjaśnienie kodu

1. Podobnie jak w przypadku poprzedniej funkcji usuwania, najpierw sprawdź, czy lista jest pusta. Jeśli tak, nie można usunąć żadnego elementu.
2. dwa wskaźniki przypisane są określone pozycje umożliwiające zlokalizowanie elementu do usunięcia.
3. Wskaźniki przesuwają się jeden po drugim (temp. poprzednich szlaków).
4. Przechodzenie jest kontynuowane aż do momentu znalezienia elementu docelowego lub aż kolejny wskaźnik osiągnie ostatni węzeł.

    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;

Wyjaśnienie programu

1. Jeśli użytkownik przeszuka całą listę powiązaną i nie znajdzie elementu docelowego, wyświetli komunikat „Element nie został znaleziony”.
2. W przeciwnym wypadku element zostanie odłączony i zwolniony w krokach 3 i 4.
3. Poprzedni wskaźnik jest połączony z węzłem wskazywanym przez następny wskaźnik temp (węzeł następujący po usuwanym).
4. Następnie wskaźnik temperatury zostaje zwolniony.

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

Wyjaśnienie kodu

1. Przeglądanie nie jest możliwe, jeśli nie ma żadnych węzłów — użytkownik musi najpierw przydzielić lub wstawić węzeł.
2. Jeżeli istnieje tylko jeden węzeł, nie jest wymagane żadne przechodzenie — zawartość węzła jest drukowana bezpośrednio, a pętla while nie jest wykonywana.
3. Jeżeli istnieje więcej niż jeden węzeł, tymczasowa drukarka drukuje każdy element aż do ostatniego.
4. W momencie osiągnięcia ostatniego elementu pętla kończy się, a funkcja zwraca sterowanie do funkcji main().

Zastosowania cyklicznej listy połączonej

• Implementacja planowania okrężnego w procesach systemowych i planowania okrężnego w szybkiej grafice.
• Harmonogramowanie token-ring w sieciach komputerowych.
• Stosowane w urządzeniach wyświetlających, takich jak cyfrowe tablice sklepowe, które wymagają ciągłego przepływu danych.

FAQ