Circulair gekoppelde lijst: voor- en nadelen

Wat is een circulair gekoppelde lijst?

Een circulaire gekoppelde lijst is een reeks knooppunten die zo zijn gerangschikt dat elk knooppunt opnieuw kan worden benaderd.tracnaar zichzelf. Elk "knooppunt" is een zelfverwijzend element met verwijzingen naar een of twee knooppunten in de directe omgeving.

Hieronder ziet u een afbeelding van een cirkelvormige gekoppelde lijst met 3 knooppunten.

Hier zie je dat elk knooppunt opnieuw wordt geladen.tracin staat om zichzelf te koppelen. Het bovenstaande voorbeeld is een circulaire enkelvoudig gekoppelde lijst.

Opmerking: De eenvoudigste circulaire gekoppelde lijst bestaat uit één knooppunt waarvan de volgende aanwijzer traces keert terug naar zichzelf, zoals hieronder weergegeven.

Basic Operaties in circulaire gekoppelde lijsten

De drie basisbewerkingen op een circulaire gekoppelde lijst zijn:

1. Invoeging
2. Verwijdering en
3. traversal

• Invoegen is het proces waarbij een knooppunt op een specifieke positie in de circulair gekoppelde lijst wordt geplaatst.
• Verwijderen is het proces waarbij een bestaand knooppunt uit de gekoppelde lijst wordt verwijderd. Het knooppunt kan worden geïdentificeerd door het voorkomen van zijn waarde of door zijn positie.
• Het doorlopen van een circulaire gekoppelde lijst is het proces waarbij de volledige inhoud van de gekoppelde lijst wordt weergegeven en opnieuw wordt geïnterpreteerd.tracterugkeren naar het bronknooppunt.

In het volgende gedeelte wordt uitgelegd hoe invoegen werkt en welke twee soorten invoegingen mogelijk zijn in een circulaire, enkelvoudig gekoppelde lijst.

Invoeging Operatie

Je maakt eerst een knooppunt aan waarvan de volgende pointer terugwijst naar zichzelf, zoals hieronder weergegeven. Zonder dit startknooppunt wordt de eerste invoeging het eerste knooppunt in de lijst.

Vervolgens zijn er twee mogelijkheden:

• Invoegen op de huidige positie in de circulaire gekoppelde lijst. Dit komt overeen met invoegen aan het begin of het einde van een gewone enkelvoudig gekoppelde lijst; in een circulaire gekoppelde lijst zijn het begin en het einde hetzelfde punt.
• Invoeging na een geïndexeerd knooppunt. Het knooppunt moet worden geïdentificeerd door een indexnummer dat overeenkomt met de elementwaarde ervan.

Om een ​​element aan het begin of einde van de circulaire gekoppelde lijst in te voegen – dat wil zeggen, op de positie waar het allereerste knooppunt werd toegevoegd – volg je de onderstaande stappen:

• U zult de bestaande zelfkoppeling met het bestaande knooppunt moeten verbreken
• De volgende aanwijzer van het nieuwe knooppunt zal linken naar het bestaande knooppunt.
• De volgende aanwijzer van het laatste knooppunt wijst naar het ingevoegde knooppunt.

LET OP: De aanwijzer die het begin of einde van de cirkel markeert, kan aan elk willekeurig knooppunt worden toegewezen. Een doorloop zal nog steeds naar hetzelfde knooppunt terugkeren, zoals later in dit artikel wordt besproken.

De stappen in (a) i-iii worden hieronder weergegeven:

(Bestaand knooppunt)

Stap 1) Verbreek de bestaande link

Stap 2) Maak een voorwaartse link (van een nieuw knooppunt naar een bestaand knooppunt)

Stap 3) Maak een luskoppeling naar het eerste knooppunt

Vervolgens probeert u invoeging na een knooppunt.

Voeg bijvoorbeeld “VALUE2” in na het knooppunt met “VALUE0”, ervan uitgaande dat het startpunt het knooppunt met “VALUE0” is.

• Verbreek de verbinding tussen het eerste en tweede knooppunt en plaats het knooppunt met "VALUE2" ertussen.
• De 'next'-pointer van het eerste knooppunt verwijst naar het nieuwe knooppunt, en de 'next'-pointer van het nieuwe knooppunt verwijst naar wat voorheen het tweede knooppunt was.
• De rest van de opstelling blijft ongewijzigd. Alle knooppunten worden opnieuw ingesteld.tracin staat om voor zichzelf te zorgen.

LET OP: Omdat de structuur cyclisch is, is de procedure voor het invoegen van een knooppunt identiek, ongeacht de gekozen positie. De aanwijzer die de cyclus sluit, gedraagt ​​zich als elke andere aanwijzer in de lijst.

Dit wordt hieronder weergegeven:

(Laten we zeggen dat er maar twee knooppunten zijn. Dit is een triviaal geval)

Stap 1) Verwijder de binnenste link tussen de verbonden knooppunten

Stap 2) Verbind het linkerknooppunt met het nieuwe knooppunt

Stap 3) Verbind het nieuwe knooppunt met het rechterknooppunt.

Recht op verwijdering Operatie

Stel dat we een circulaire gelinkte lijst met 3 knooppunten hebben. De twee verwijderingsgevallen zijn:

• Het huidige element verwijderen
• Verwijdering na een element.

Verwijdering aan het begin/einde:

1. Ga vanaf het laatste knooppunt naar het eerste knooppunt.
2. Verwijderen vanaf het einde vereist slechts één doorloopstap, van het laatste knooppunt naar het eerste knooppunt.
3. Verwijder de link tussen het laatste knooppunt en het eerste knooppunt.
4. Koppel het laatste knooppunt aan het volgende element van het eerste knooppunt.
5. Maak het eerste knooppunt vrij.

(Bestaande opstelling)

Stap 1) Verwijder de circulaire link

Stap 2) Verwijder de link tussen de eerste en de volgende, koppel het laatste knooppunt aan het knooppunt dat volgt op de eerste

Stap 3) De eerste node vrijgeven/dealloceren

Verwijderen na een knooppunt:

1. Doorloop de lus totdat het volgende knooppunt het knooppunt is dat verwijderd moet worden.
2. Ga naar het volgende knooppunt en plaats een aanwijzer op het vorige knooppunt.
3. Verbind het vorige knooppunt met het knooppunt na het huidige knooppunt, met behulp van de volgende aanwijzer.
4. Maak het huidige (ontkoppelde) knooppunt vrij.

Stap 1) Laten we zeggen dat we een knooppunt met 'VALUE1' moeten verwijderen.

Stap 2) Verwijder de link tussen het vorige knooppunt en het huidige knooppunt en verbind het vorige knooppunt vervolgens rechtstreeks met het knooppunt waarnaar de volgende aanwijzer van het huidige knooppunt wijst (het knooppunt na VALUE1).

Stap 3) Maak het huidige knooppunt vrij of maak de toewijzing ervan ongedaan.

Doorkruising van een circulair gekoppelde lijst

Om een ​​circulaire gelinkte lijst te doorlopen vanaf een pointer naar het laatste element, controleer je eerst of die pointer NULL is. Als dat niet het geval is, controleer je of de lijst slechts één element bevat. Zo niet, doorloop je de lijst dan met een tijdelijke pointer totdat je de pointer naar het laatste element weer bereikt, zoals in de onderstaande animatie te zien is.

Voordelen van circulair gekoppelde lijst

Enkele voordelen van circulair gekoppelde lijsten zijn:

1. Geen vereiste voor een NULL-toewijzing in de code. De cirkelvormige lijst verwijst nooit naar een NULL-aanwijzer, tenzij de toewijzing volledig is opgeheven.
2. Circulaire gekoppelde lijsten zijn voordelig voor bewerkingen aan het einde van de lijst, omdat het begin en het einde samenvallen. Algorithms Bij round-robin-planning kunnen processen in de wachtrij soepel worden verwerkt, zonder dat er zwevende of NULL-pointers worden tegengekomen.
3. Een circulaire gekoppelde lijst ondersteunt nog steeds alle reguliere bewerkingen van een enkelvoudig gekoppelde lijst. dubbel gekoppelde lijst Het kan zelfs de noodzaak wegnemen om de hele lijst te doorlopen om een ​​element te vinden — in het ergste geval bevindt het doel zich tegenover de startpointer, waardoor er maximaal de helft van de lijst hoeft te worden doorlopen.

Nadelen van circulair gekoppelde lijst

De nadelen van het gebruik van een circulair gekoppelde lijst zijn hieronder:

1. Cirkelvormige lijsten zijn complexer dan enkelvoudig gelinkte lijsten.
2. RevHet omkeren van een circulaire lijst is complexer dan het omkeren van een enkelvoudig of dubbelvoudig gekoppelde lijst.
3. Als de beëindiging van een lus niet zorgvuldig wordt afgehandeld, kan de doorloopcode in een oneindige lus terechtkomen.
4. Het is lastiger om het einde van de lijst te vinden en de juiste lusbesturingsvoorwaarden te schrijven.
5. Het invoegen aan het begin vereist (vanuit implementatieperspectief) het doorlopen van de hele lijst om het laatste knooppunt te bereiken.

Enkelvoudig gekoppelde lijst als circulair gekoppelde lijst

U wordt aangemoedigd de onderstaande C-code te lezen en te implementeren. Deze code illustreert de pointer-rekenkunde die hoort bij een circulaire enkelvoudig gekoppelde lijst.

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

Toelichting code:

1. De eerste twee regels code zijn de noodzakelijke meegeleverde headerbestanden.
2. In het volgende gedeelte wordt de structuur van elk zelfverwijzend knooppunt gedefinieerd. Het bevat een waarde en een aanwijzer van hetzelfde type als de structuur.
3. Elke structuurinstantie is gekoppeld aan andere structuurobjecten van hetzelfde type.
4. Er zijn verschillende functieprototypes voor:
   1. Een element toevoegen aan een lege gekoppelde lijst
   2. Invoegen bij de momenteel gericht positie van een circulair gekoppelde lijst.
   3. Invoegen na een bepaalde geïndexeerd waarde in de gekoppelde lijst.
   4. Verwijderen/verwijderen na een bepaalde geïndexeerd waarde in de gekoppelde lijst.
   5. Verwijderen op de momenteel aangewezen positie van een cirkelvormig gekoppelde lijst
5. De laatste functie drukt elk element af via een cirkelvormige doorgang in elke status van de gekoppelde lijst.

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)

Toelichting code:

1. Voor de addToEmpty-code moet je een lege node toewijzen met behulp van de malloc()-functie.
2. Plaats de binnenkomende gegevens in het tijdelijke knooppunt.
3. Wijs het tijdelijke knooppunt als laatste toe en stel de volgende aanwijzer ervan in op zichzelf, zodat het enkele knooppunt weer naar zichzelf wijst.
4. Geef de laatste pointer terug naar de main() / applicatiecontext.

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

Uitleg van code

1. Als de lijst leeg is, geef dan de controle door aan addToEmpty() en geef de controle terug.
2. Maak een tijdelijk knooppunt aan dat na het huidige knooppunt wordt geplaatst.
3. Verbind de aanwijzers zoals weergegeven in het bovenstaande diagram.
4. Retourneer de laatste pointer die overeenkomt met het patroon dat in de vorige functie is gebruikt.

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

Toelichting code:

1. Als de lijst leeg is, negeer dan de zoekterm, voeg het huidige item toe als enige element in de lijst en geef de controle terug.
2. In elke iteratie van de do-while-lus bevat een pointer naar de vorige waarde het laatst doorlopen resultaat.
3. Pas dan vindt de volgende doorloopstap plaats.
4. De do-while-lus eindigt wanneer de doelgegevens zijn gevonden of wanneer temp de laatste pointer weer bereikt. Het volgende codeblok bepaalt wat er met het gevonden item moet gebeuren.

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

Toelichting code:

1. Als de hele lijst is doorlopen maar het item niet is gevonden, toon dan de melding "Element niet gevonden" en geef de controle terug aan de aanroeper.
2. Als het doelknooppunt is gevonden, wijs dan een nieuw knooppunt toe voor de in te voegen waarde.
3. Link De pointer van het vorige knooppunt naar het nieuwe knooppunt koppelen, en de pointer van het nieuwe knooppunt naar 'next' verbinden met 'temp' (de traverseringsvariabele).
4. Hierdoor wordt het nieuwe element direct na het doelknooppunt in de circulaire gekoppelde lijst geplaatst. De controle keert vervolgens terug naar de aanroeper.

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)

Uitleg van code

1. Om het laatste (huidige) knooppunt te verwijderen, moet je eerst controleren of de lijst leeg is. Zo ja, dan kan er geen element worden verwijderd.
2. De tijdelijke variabele schuift één schakel verder.
3. Verbind de laatste aanwijzer met het knooppunt na het eerste knooppunt.
4. Maak de tijdelijke pointer vrij om het niet-gekoppelde knooppunt te dealloceren.

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

Uitleg van code

1. Net als bij de vorige verwijderingsfunctie, controleer eerst of de lijst leeg is. Zo ja, dan kan er geen element worden verwijderd.
2. Twee pointers krijgen specifieke posities toegewezen om het te verwijderen element te lokaliseren.
3. De aanwijzers worden één voor één vooruitgeschoven (vorige trails temp).
4. De doorloop gaat door totdat het doelelement is gevonden of de volgende aanwijzer het laatste knooppunt weer bereikt.

    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;

Uitleg programma

1. Als de volledige gekoppelde lijst wordt doorlopen zonder het doel te vinden, wordt de melding "Element niet gevonden" weergegeven.
2. Anders wordt het element in stap 3 en 4 ontkoppeld en vrijgegeven.
3. De vorige pointer is gekoppeld aan het knooppunt waarnaar de volgende pointer van temp wijst (het knooppunt na het knooppunt dat wordt verwijderd).
4. De tijdelijke aanwijzer wordt vervolgens vrijgegeven.

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

Uitleg van code

1. De peek-traversal is niet mogelijk als er nul knooppunten zijn; de gebruiker moet eerst een knooppunt toewijzen of invoegen.
2. Als er maar één knooppunt is, is er geen doorloop nodig — de inhoud van het knooppunt wordt direct afgedrukt en de while-lus wordt niet uitgevoerd.
3. Als er meer dan één knooppunt is, print temp elk item tot en met het laatste element.
4. Zodra het laatste element is bereikt, eindigt de lus en geeft de functie de controle terug aan main().

Toepassingen van de Circular Linked List

• Implementatie van round-robin planning in systeemprocessen en circulaire planning in high-speed graphics.
• Token-ring planning in computernetwerken.
• Gebruikt in weergave-eenheden zoals digitale winkelborden die een continue gegevensstroom vereisen.

Veelgestelde vragen