Circulair gekoppelde lijst: voor- en nadelen

Wat is een circulair gekoppelde lijst?

Een circulair gekoppelde lijst is een reeks knooppunten die zo zijn gerangschikt dat elk knooppunt naar zichzelf kan worden herleid. Hier is een “knooppunt” een zelfreferentieel 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 kun je zien dat elk knooppunt naar zichzelf herleidbaar is. Het bovenstaande voorbeeld is een cirkelvormige, enkelvoudig gekoppelde lijst.

Opmerking: de eenvoudigste cirkelvormig gekoppelde lijst is een knooppunt dat alleen naar zichzelf verwijst, zoals weergegeven

Basic Operain circulair gekoppelde lijsten

De 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 circulair gekoppelde lijst is het proces waarbij de volledige inhoud van de gekoppelde lijst wordt weergegeven en teruggevoerd wordt naar het bronknooppunt.

In de volgende sectie zult u het invoegen van een knooppunt begrijpen, en de soorten invoeging die mogelijk zijn in een Circular Singly Linked List.

Invoeging Operatie

In eerste instantie moet u één knooppunt maken dat naar zichzelf wijst, zoals weergegeven in deze afbeelding. Zonder dit knooppunt wordt bij het invoegen het eerste knooppunt gemaakt.

Vervolgens zijn er twee mogelijkheden:

• Invoeging op de huidige positie van de circulair gekoppelde lijst. Dit komt overeen met het invoegen aan het begin van het einde van een reguliere enkelvoudige gekoppelde lijst. In een circulair gekoppelde lijst zijn het begin en het einde hetzelfde.
• Invoeging na een geïndexeerd knooppunt. Het knooppunt moet worden geïdentificeerd door een indexnummer dat overeenkomt met de elementwaarde ervan.

Voor invoeging aan het begin/einde van de circulair gekoppelde lijst, dat wil zeggen op de positie waar het allereerste knooppunt ooit is toegevoegd,

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

OPMERKING: De aanwijzer die de tokenmaster of het begin/einde van de cirkel is, kan worden gewijzigd. Het zal nog steeds terugkeren naar hetzelfde knooppunt tijdens een doortocht, die verderop 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.

Laten we bijvoorbeeld “VALUE2” invoegen na het knooppunt met “VALUE0”. Laten we aannemen dat het startpunt het knooppunt met “VALUE0” is.

• U moet de lijn tussen het eerste en het tweede knooppunt doorbreken en het knooppunt met “VALUE2” ertussen plaatsen.
• De volgende aanwijzer van het eerste knooppunt moet naar dit knooppunt linken, en de volgende aanwijzer van dit knooppunt moet naar het eerdere tweede knooppunt verwijzen.
• De rest van de regeling blijft ongewijzigd. Alle knooppunten zijn naar zichzelf herleidbaar.

OPMERKING: Omdat er sprake is van een cyclische opstelling, geldt bij het invoegen van een knooppunt voor elk knooppunt dezelfde procedure. De aanwijzer die een cyclus voltooit, voltooit de cyclus net als elk ander knooppunt.

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.

verwijdering Operatie

Laten we uitgaan van een cirkelvormig gekoppelde lijst met drie knooppunten. De gevallen voor verwijdering worden hieronder gegeven:

• Het huidige element verwijderen
• Verwijdering na een element.

Verwijdering aan het begin/einde:

1. Ga vanaf het laatste knooppunt naar het eerste knooppunt.
2. Om vanaf het einde te verwijderen, mag er slechts één verplaatsingsstap zijn, van het laatste knooppunt naar het eerste knooppunt.
3. Verwijder de link tussen het laatste knooppunt en het volgende 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 ronde schakel

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

STAP 3) Maak het eerste knooppunt vrij /deallocate

Verwijderen na een knooppunt:

1. Ga door totdat het volgende knooppunt het knooppunt is dat moet worden verwijderd.
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 koppeling tussen het vorige knooppunt en het huidige knooppunt. Koppel het vorige knooppunt aan het volgende knooppunt dat door het huidige knooppunt wordt aangewezen (met VALUE1).

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

Doorkruising van een circulair gekoppelde lijst

Om een ​​circulaire gekoppelde lijst te doorkruisen, beginnend bij een laatste pointer, controleer of de laatste pointer zelf NULL is. Als deze voorwaarde onwaar is, controleer dan of er slechts één element is. Anders, doorkruis met behulp van een tijdelijke pointer totdat de laatste pointer weer is bereikt, of zo vaak als nodig is, zoals getoond in de GIF hieronder.

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. Circulair gekoppelde lijsten zijn voordelig voor eindbewerkingen, omdat begin en einde samenvallen. Algorithms zoals de Round Robin-planning kan processen die op een circulaire manier in de wachtrij staan ​​netjes elimineren zonder bungelende of NULL-referentiële verwijzingen tegen te komen.
3. Een circulair gekoppelde lijst vervult ook alle reguliere functies van een enkelvoudig gekoppelde lijst. In feite circulair dubbel gelinkte lijsten hieronder besproken kan zelfs de noodzaak elimineren van een volledige verplaatsing om een ​​element te lokaliseren. Dat element zou hoogstens precies het tegenovergestelde zijn van het begin en slechts de helft van de gekoppelde lijst voltooien.

Nadelen van circulair gekoppelde lijst

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

1. Circulaire lijsten zijn complex vergeleken met enkelvoudig gelinkte lijsten.
2. RevHet gebruik van een circulaire lijst is complexer dan enkelvoudige of dubbele lijsten.
3. Als er niet zorgvuldig mee wordt omgegaan, kan de code in een oneindige lus terechtkomen.
4. Moeilijker om het einde van de lijst en luscontrole te vinden.
5. Als we bij Start invoegen, moeten we de volledige lijst doorlopen om het laatste knooppunt te vinden. (Implementatieperspectief)

Enkelvoudig gekoppelde lijst als circulair gekoppelde lijst

U wordt aangemoedigd om te proberen de onderstaande code te lezen en te implementeren. Het presenteert de pointer-berekeningen die verband houden met circulair gekoppelde lijsten.

#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 zelfreferentieel knooppunt beschreven. Het bevat een waarde en een aanwijzer van hetzelfde type als de structuur.
3. Elke structuur linkt herhaaldelijk naar 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. Wijs voor de addEmpty-code een leeg knooppunt toe met behulp van de malloc-functie.
2. Voor dit knooppunt plaatst u de gegevens in de variabele temp.
3. Wijs de enige variabele toe en koppel deze aan de variabele temp
4. Retourneer het laatste element 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 er geen element is om in te voegen, moet u ervoor zorgen dat u het aan een lege lijst toevoegt en de controle retourneert.
2. Maak een tijdelijk element om na het huidige element te plaatsen.
3. Verbind de wijzers zoals weergegeven.
4. Retourneert de laatste aanwijzer zoals in de vorige functie.

...
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 er geen element in de lijst staat, negeert u de gegevens, voegt u het huidige item toe als het laatste item in de lijst en geeft u de controle terug
2. Zorg er voor elke iteratie in de do-while-lus voor dat er een eerdere aanwijzer is die het laatst doorlopen resultaat bevat.
3. Alleen dan kan de volgende doortocht plaatsvinden.
4. Als de gegevens worden gevonden of als de temperatuur teruggaat naar de laatste pointer, wordt de do-while beëindigd. Het volgende codegedeelte bepaalt wat er met het 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 en het item nog niet is gevonden, geeft u het bericht 'Item niet gevonden' weer en geeft u de controle terug aan de beller.
2. Als er een knooppunt is gevonden en/of het knooppunt nog niet het laatste knooppunt is, maak dan een nieuw knooppunt aan.
3. Link het vorige knooppunt met het nieuwe knooppunt. Koppel het huidige knooppunt aan temp (de traversale variabele).
4. Dit zorgt ervoor dat het element na een bepaald knooppunt in de circulair gekoppelde lijst wordt geplaatst. Keer terug naar de beller.

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 alleen het laatste (huidige) knooppunt te verwijderen, controleert u of deze lijst leeg is. Als dit het geval is, kan geen enkel element worden verwijderd.
2. De variabele temp doorloopt slechts één link vooruit.
3. Koppel de laatste aanwijzer aan de aanwijzer na de eerste.
4. Bevrijd de temperatuuraanwijzer. Het maakt de niet-gekoppelde laatste aanwijzer ongedaan.

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. Controleer net als bij de vorige verwijderingsfunctie of er geen element is. Als dit waar is, kan geen enkel element worden verwijderd.
2. Pointers krijgen specifieke posities toegewezen om het te verwijderen element te lokaliseren.
3. De wijzers zijn naar voren geschoven, achter elkaar. (vorig achter temp)
4. Het proces gaat door totdat een element wordt gevonden, of het volgende element terugkeert naar de laatste aanwijzer.

    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 het element wordt gevonden nadat de volledige gekoppelde lijst is doorlopen, verschijnt er een foutmelding dat het item niet is gevonden.
2. Anders wordt het element losgekoppeld en vrijgegeven in stap 3 en 4.
3. De vorige pointer is gekoppeld aan het adres dat door het te verwijderen element (temp) als “volgende” wordt aangegeven.
4. De temperatuuraanwijzer wordt daarom ongedaan gemaakt en 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. Het kijken of doorlopen is niet mogelijk als er nul nodig is. De gebruiker moet een knooppunt toewijzen of invoegen.
2. Als er slechts één knooppunt is, hoeft er niet doorheen te worden gelopen, kan de inhoud van het knooppunt worden afgedrukt en wordt de while-lus niet uitgevoerd.
3. Als er meer dan één knooppunt is, drukt de temperatuur het hele item af tot het laatste element.
4. Op het moment dat het laatste element wordt bereikt, eindigt de lus en keert de functie terug naar de hoofdfunctie.

Toepassingen van de Circular Linked List

• Implementatie van round-robin planning in systeemprocessen en circulaire planning in high-speed graphics.
• Tokenringplanning in computernetwerken.
• Het wordt gebruikt in display-units zoals winkelborden, waarbij de gegevens continu moeten worden doorzocht.