Zirkuläre verknüpfte Liste: Vor- und Nachteile

Was ist eine zirkulär verknüpfte Liste?

Eine zirkulär verknüpfte Liste ist eine Folge von Knoten, die so angeordnet sind, dass jeder Knoten auf sich selbst zurückgeführt werden kann. Hier ist ein „Knoten“ ein selbstreferenzielles Element mit Zeigern auf einen oder zwei Knoten in seiner unmittelbaren Nähe.

Unten sehen Sie eine Darstellung einer kreisförmigen verknüpften Liste mit drei Knoten.

Hier sehen Sie, dass jeder Knoten auf sich selbst zurückführbar ist. Das oben gezeigte Beispiel ist eine kreisförmige, einfach verknüpfte Liste.

Hinweis: Die einfachste zirkulär verknüpfte Liste ist ein Knoten, der sich wie gezeigt nur auf sich selbst bezieht

Grundlagen Operationen in zirkulär verknüpften Listen

Die grundlegenden Operationen auf einer zirkulär verknüpften Liste sind:

1. Einfügen
2. Löschung und
3. Traversal

• Beim Einfügen wird ein Knoten an einer bestimmten Position in der kreisförmig verknüpften Liste platziert.
• Beim Löschen wird ein vorhandener Knoten aus der verknüpften Liste entfernt. Der Knoten kann durch das Auftreten seines Wertes oder durch seine Position identifiziert werden.
• Beim Durchlaufen einer zirkulär verknüpften Liste wird der gesamte Inhalt der verknüpften Liste angezeigt und zum Quellknoten zurückverfolgt.

Im nächsten Abschnitt lernen Sie das Einfügen eines Knotens und die möglichen Einfügungsarten in einer kreisförmigen einfach verknüpften Liste kennen.

Einfügen OperaProduktion

Zunächst müssen Sie einen Knoten erstellen, der auf sich selbst zeigt, wie in diesem Bild gezeigt. Ohne diesen Knoten wird beim Einfügen der erste Knoten erstellt.

Als nächstes gibt es zwei Möglichkeiten:

• Einfügung an der aktuellen Position der zirkulären verknüpften Liste. Dies entspricht dem Einfügen am Anfang und Ende einer regulären singulären verknüpften Liste. In einer zirkulär verknüpften Liste sind Anfang und Ende gleich.
• Einfügung nach einem indizierten Knoten. Der Knoten sollte durch eine Indexnummer identifiziert werden, die seinem Elementwert entspricht.

Zum Einfügen am Anfang/Ende der zirkulär verknüpften Liste, also an der Position, an der der allererste Knoten hinzugefügt wurde,

• Sie müssen die bestehende Selbstverknüpfung zum bestehenden Knoten unterbrechen
• Der nächste Zeiger des neuen Knotens wird auf den vorhandenen Knoten verweisen.
• Der nächste Zeiger des letzten Knotens zeigt auf den eingefügten Knoten.

HINWEIS: Der Zeiger, der der Token-Master oder der Anfang/Ende des Kreises ist, kann geändert werden. Bei einer Durchquerung wird es immer noch zum selben Knoten zurückkehren, was weiter unten besprochen wird.

Die Schritte in (a) i-iii sind unten dargestellt:

(Vorhandener Knoten)

SCHRITT 1) Unterbrechen Sie den vorhandenen Link

SCHRITT 2) Erstellen Sie einen Forward-Link (von einem neuen Knoten zu einem vorhandenen Knoten).

SCHRITT 3) Erstellen Sie eine Schleifenverbindung zum ersten Knoten

Als Nächstes versuchen Sie, nach einem Knoten einzufügen.

Fügen wir beispielsweise „VALUE2“ nach dem Knoten mit „VALUE0“ ein. Nehmen wir an, dass der Ausgangspunkt der Knoten mit „VALUE0“ ist.

• Sie müssen die Linie zwischen dem ersten und zweiten Knoten durchbrechen und den Knoten mit „VALUE2“ dazwischen platzieren.
• Der nächste Zeiger des ersten Knotens muss auf diesen Knoten verweisen, und der nächste Zeiger dieses Knotens muss auf den früheren zweiten Knoten verweisen.
• Die übrige Regelung bleibt unverändert. Alle Knoten sind auf sich selbst zurückführbar.

HINWEIS: Da es sich um eine zyklische Anordnung handelt, erfordert das Einfügen eines Knotens für jeden Knoten den gleichen Vorgang. Der Zeiger, der einen Zyklus abschließt, schließt den Zyklus wie jeder andere Knoten ab.

Dies ist unten dargestellt:

(Nehmen wir an, es gibt nur zwei Knoten. Das ist ein trivialer Fall)

SCHRITT 1) Entfernen Sie die innere Verbindung zwischen den verbundenen Knoten

SCHRITT 2) Verbinden Sie den Knoten auf der linken Seite mit dem neuen Knoten

SCHRITT 3) Verbinden Sie den neuen Knoten mit dem Knoten auf der rechten Seite.

Streichung OperaProduktion

Nehmen wir eine zirkulär verknüpfte Liste mit drei Knoten an. Nachfolgend sind die Löschungsfälle aufgeführt:

• Löschen des aktuellen Elements
• Löschung nach einem Element.

Löschung am Anfang/Ende:

1. Vom letzten Knoten zum ersten Knoten wechseln.
2. Um vom Ende zu löschen, sollte es nur einen Durchlaufschritt geben, vom letzten Knoten zum ersten Knoten.
3. Löschen Sie die Verbindung zwischen dem letzten Knoten und dem nächsten Knoten.
4. Verknüpfen Sie den letzten Knoten mit dem nächsten Element des ersten Knotens.
5. Geben Sie den ersten Knoten frei.

(Bestehendes Setup)

STEP 1) Entfernen Sie den kreisförmigen Link

SCHRITTE 2) Entfernen Sie die Verknüpfung zwischen dem ersten und dem nächsten Knoten und verknüpfen Sie den letzten Knoten mit dem Knoten, der dem ersten folgt.

SCHRITT 3) Geben Sie den ersten Knoten frei bzw. geben Sie die Zuordnung frei

Löschen nach einem Knoten:

1. Durchlaufen, bis der nächste Knoten der zu löschende Knoten ist.
2. Gehen Sie zum nächsten Knoten und platzieren Sie einen Zeiger auf dem vorherigen Knoten.
3. Verbinden Sie den vorherigen Knoten mithilfe seines nächsten Zeigers mit dem Knoten nach dem aktuellen Knoten.
4. Gibt den aktuellen (entkoppelten) Knoten frei.

SCHRITT 1) Nehmen wir an, wir müssen einen Knoten mit „VALUE1“ löschen.

SCHRITT 2) Entfernen Sie die Verknüpfung zwischen dem vorherigen Knoten und dem aktuellen Knoten. Verknüpfen Sie den vorherigen Knoten mit dem nächsten Knoten, auf den der aktuelle Knoten zeigt (mit VALUE1).

SCHRITT 3) Geben Sie den aktuellen Knoten frei oder geben Sie ihn frei.

Durchlaufen einer zirkulär verknüpften Liste

Um eine zirkuläre verknüpfte Liste ausgehend von einem letzten Zeiger zu durchlaufen, prüfen Sie, ob der letzte Zeiger selbst NULL ist. Wenn diese Bedingung falsch ist, prüfen Sie, ob nur ein Element vorhanden ist. Andernfalls durchlaufen Sie die Liste mit einem temporären Zeiger, bis der letzte Zeiger erneut erreicht wird, oder so oft wie nötig, wie im GIF unten gezeigt.

Vorteile einer zirkulären verknüpften Liste

Einige der Vorteile von zirkulär verknüpften Listen sind:

1. Keine Anforderung für eine NULL-Zuweisung im Code. Die zirkuläre Liste zeigt niemals auf einen NULL-Zeiger, es sei denn, die Zuordnung wird vollständig aufgehoben.
2. Zirkuläre verknüpfte Listen sind für Endoperationen vorteilhaft, da Anfang und Ende zusammenfallen. Algorithms Beispielsweise kann die Round-Robin-Planung Prozesse, die kreisförmig in die Warteschlange gestellt werden, sauber eliminieren, ohne auf leere oder NULL-referenzielle Zeiger zu stoßen.
3. Eine zirkulär verknüpfte Liste führt auch alle regulären Funktionen einer einfach verknüpften Liste aus. Tatsächlich kreisförmig doppelt verknüpfte Listen Die unten besprochene Methode kann sogar die Notwendigkeit einer vollständigen Durchquerung zum Auffinden eines Elements überflüssig machen. Dieses Element würde höchstens genau gegenüber dem Anfang stehen und nur die Hälfte der verknüpften Liste vervollständigen.

Nachteile der zirkulären verknüpften Liste

Die Nachteile bei der Verwendung einer zirkulär verknüpften Liste sind unten aufgeführt:

1. Zirkuläre Listen sind komplex im Vergleich zu einzeln verlinkte Listen.
2. RevDie Anzahl der zirkulären Listen ist im Vergleich zu Einzel- oder Doppellisten komplexer.
3. Bei unsachgemäßer Handhabung kann der Code in eine Endlosschleife geraten.
4. Es ist schwieriger, das Ende der Liste und die Schleifensteuerung zu finden.
5. Beim Einfügen am Start müssen wir die gesamte Liste durchlaufen, um den letzten Knoten zu finden. (Implementierungsperspektive)

Einfach verknüpfte Liste als zirkulär verknüpfte Liste

Wir empfehlen Ihnen, den folgenden Code zu lesen und zu implementieren. Es stellt die Zeigerarithmetik vor, die mit zirkulär verknüpften Listen verbunden ist.

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

Erklärung des Codes:

1. Die ersten beiden Codezeilen sind die notwendigen enthaltenen Header-Dateien.
2. Im nächsten Abschnitt wird die Struktur jedes selbstreferenziellen Knotens beschrieben. Es enthält einen Wert und einen Zeiger vom gleichen Typ wie die Struktur.
3. Jede Struktur verweist wiederholt auf Strukturobjekte desselben Typs.
4. Es gibt verschiedene Funktionsprototypen für:
   1. Hinzufügen eines Elements zu einer leeren verknüpften Liste
   2. Einfügen am derzeit spitz Position einer zirkulär verknüpften Liste.
   3. Einfügen nach einer bestimmten indiziert Wert in der verknüpften Liste.
   4. Entfernen/Löschen nach einer bestimmten Zeit indiziert Wert in der verknüpften Liste.
   5. Entfernen an der aktuell angezeigten Position einer kreisförmigen verknüpften Liste
5. Die letzte Funktion druckt jedes Element durch einen kreisförmigen Durchlauf in jedem Zustand der verknüpften Liste.

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)

Erklärung des Codes:

1. Ordnen Sie für den addEmpty-Code mithilfe der malloc-Funktion einen leeren Knoten zu.
2. Platzieren Sie für diesen Knoten die Daten in der temporären Variablen.
3. Weisen Sie die einzige Variable zu und verknüpfen Sie sie mit der temporären Variablen
4. Geben Sie das letzte Element an den main()/Anwendungskontext zurück.

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

Erläuterung des Codes

1. Wenn kein Element zum Einfügen vorhanden ist, sollten Sie darauf achten, es zu einer leeren Liste hinzuzufügen und die Kontrolle zurückzugeben.
2. Erstellen Sie ein temporäres Element, das nach dem aktuellen Element platziert wird.
3. Verknüpfen Sie die Zeiger wie gezeigt.
4. Gibt den letzten Zeiger wie in der vorherigen Funktion zurück.

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

Erklärung des Codes:

1. Wenn die Liste kein Element enthält, ignorieren Sie die Daten, fügen Sie das aktuelle Element als letztes Element zur Liste hinzu und geben Sie die Kontrolle zurück
2. Stellen Sie für jede Iteration in der do-while-Schleife sicher, dass es einen vorherigen Zeiger gibt, der das zuletzt durchlaufene Ergebnis enthält.
3. Erst dann kann die nächste Durchquerung erfolgen.
4. Wenn die Daten gefunden werden oder temp bis zum letzten Zeiger zurückreicht, wird das Do-While beendet. Der nächste Codeabschnitt entscheidet, was mit dem Element geschehen soll.

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

Erklärung des Codes:

1. Wenn die gesamte Liste durchlaufen wurde, das Element jedoch nicht gefunden wird, zeigen Sie die Meldung „Element nicht gefunden“ an und geben Sie dann die Kontrolle an den Aufrufer zurück.
2. Wenn ein Knoten gefunden wird und/oder der Knoten noch nicht der letzte Knoten ist, erstellen Sie einen neuen Knoten.
3. Link den vorherigen Knoten durch den neuen Knoten. Verknüpfen Sie den aktuellen Knoten mit temp (der Traversalvariablen).
4. Dadurch wird sichergestellt, dass das Element nach einem bestimmten Knoten in der zirkulär verknüpften Liste platziert wird. Kehren Sie zum Anrufer zurück.

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)

Erläuterung des Codes

1. Um nur den letzten (aktuellen) Knoten zu entfernen, prüfen Sie, ob diese Liste leer ist. Wenn dies der Fall ist, kann kein Element entfernt werden.
2. Die temporäre Variable durchläuft nur einen Link vorwärts.
3. Verknüpfen Sie den letzten Zeiger mit dem Zeiger nach dem ersten.
4. Geben Sie den temporären Zeiger frei. Es gibt den nicht verknüpften letzten Zeiger frei.

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

Erläuterung des Codes

1. Überprüfen Sie wie bei der vorherigen Entfernungsfunktion, ob kein Element vorhanden ist. Wenn dies zutrifft, kann kein Element entfernt werden.
2. Pointers werden bestimmte Positionen zugewiesen, um das zu löschende Element zu lokalisieren.
3. Die Zeiger werden hintereinander vorgeschoben. (vorher hinter temp)
4. Der Prozess wird fortgesetzt, bis ein Element gefunden wird oder das nächste Element zum letzten Zeiger zurückkehrt.

    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;	

Erläuterung des Programms

1. Wenn das Element nach dem Durchlaufen der gesamten verknüpften Liste gefunden wurde, wird eine Fehlermeldung angezeigt, die besagt, dass das Element nicht gefunden wurde.
2. Andernfalls wird in den Schritten 3 und 4 die Verknüpfung und Freigabe des Elements vorgenommen.
3. Der vorherige Zeiger ist mit der Adresse verknüpft, auf die das zu löschende Element (temp) als „nächste“ zeigt.
4. Der temporäre Zeiger wird daher freigegeben und freigegeben.

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

Erläuterung des Codes

1. Der Blick oder die Durchquerung ist nicht möglich, wenn null benötigt werden. Der Benutzer muss einen Knoten zuweisen oder einfügen.
2. Wenn nur ein Knoten vorhanden ist, ist kein Durchlaufen erforderlich, der Inhalt des Knotens kann gedruckt werden und die while-Schleife wird nicht ausgeführt.
3. Wenn es mehr als einen Knoten gibt, druckt der Temp das gesamte Element bis zum letzten Element.
4. Sobald das letzte Element erreicht ist, wird die Schleife beendet und die Funktion ruft wieder die Hauptfunktion auf.

Anwendungen der Circular Linked List

• Implementierung der Round-Robin-Planung in Systemprozessen und der kreisförmigen Planung in Hochgeschwindigkeitsgrafiken.
• Token-Ring-Planung in Computernetzwerken.
• Es wird in Anzeigeeinheiten wie Shopboards verwendet, die einen kontinuierlichen Datendurchlauf erfordern.