circular linked list data structure c with illustration
Een compleet overzicht van circulaire gekoppelde lijst.
Een circulaire gekoppelde lijst is een variatie op de gekoppelde lijst. Het is een gekoppelde lijst waarvan de knooppunten zo met elkaar zijn verbonden dat het een cirkel vormt.
In de circulaire gekoppelde lijst wordt de volgende pointer van het laatste knooppunt niet op nul gezet, maar bevat deze het adres van het eerste knooppunt en vormt zo een cirkel.
Bezoek hier om C ++ vanaf het begin te leren.
Wat je leert:
Circulaire gekoppelde lijst in C ++
De onderstaande indeling is voor een enkelvoudig gelinkte lijst.
Een circulaire gelinkte lijst kan een enkelvoudig gelinkte lijst of een dubbel gelinkte lijst zijn. In een dubbel cirkelvormige gekoppelde lijst is de vorige wijzer van het eerste knooppunt verbonden met het laatste knooppunt, terwijl de volgende aanwijzer van het laatste knooppunt is verbonden met het eerste knooppunt.
De weergave wordt hieronder weergegeven.
Verklaring
We kunnen een knooppunt in een circulaire gekoppelde lijst declareren als elk ander knooppunt, zoals hieronder wordt weergegeven:
Om de circulaire gekoppelde lijst te implementeren, onderhouden we een externe pointer 'laatste' die naar het laatste knooppunt in de circulaire gekoppelde lijst verwijst. Daarom zal last-> next naar het eerste knooppunt in de gekoppelde lijst wijzen.
Door dit te doen, zorgen we ervoor dat wanneer we een nieuw knooppunt aan het begin of aan het einde van de lijst invoegen, we niet de hele lijst hoeven te doorlopen. Dit komt doordat de laatste naar het laatste knooppunt wijst, terwijl laatste-> volgende naar het eerste knooppunt wijst.
Dit zou niet mogelijk zijn geweest als we de externe aanwijzer naar het eerste knooppunt hadden gewezen.
Basisbewerkingen
De circulaire gekoppelde lijst ondersteunt het invoegen, verwijderen en doorlopen van de lijst. We zullen nu elk van de operaties in detail bespreken.
Invoeging
We kunnen een knoop in een cirkelvormige gekoppelde lijst invoegen als een eerste knooppunt (lege lijst), aan het begin, aan het einde of tussen de andere knooppunten. Laten we elk van deze invoegbewerkingen bekijken met behulp van een onderstaande afbeelding.
# 1) Invoegen in een lege lijst
Als er geen knooppunten in de ronde lijst zijn en de lijst is leeg, is de laatste aanwijzer nul, dan voegen we een nieuw knooppunt N in door de laatste aanwijzer naar het knooppunt N te wijzen, zoals hierboven weergegeven. De volgende aanwijzer van N zal naar het knooppunt N zelf wijzen, aangezien er maar één knooppunt is. N wordt dus zowel het eerste als het laatste knooppunt in de lijst.
# 2) Invoegen aan het begin van de lijst
Zoals getoond in de bovenstaande weergave, wanneer we een knooppunt aan het begin van de lijst toevoegen, wijst de volgende wijzer van het laatste knooppunt naar het nieuwe knooppunt N, waardoor het een eerste knooppunt wordt.
N-> volgende = laatste-> volgende
Laatste-> volgende = N
# 3) Invoegen aan het einde van de lijst
Om een nieuw knooppunt aan het einde van de lijst in te voegen, volgen we deze stappen:
beweren () c ++
N-> volgende = laatste -> volgende;
laatste -> volgende = N
laatste = N
# 4) Invoegen tussen de lijst
Stel dat we een nieuw knooppunt N moeten invoegen tussen N3 en N4, dan moeten we eerst de lijst doorlopen en het knooppunt lokaliseren waarna het nieuwe knooppunt moet worden ingevoegd, in dit geval de N3.
Nadat het knooppunt is gevonden, voeren we de volgende stappen uit.
N -> volgende = N3 -> volgende;
N3 -> volgende = N
Dit voegt een nieuw knooppunt N in na N3.
Verwijdering
De verwijderingsoperatie van de circulaire gekoppelde lijst omvat het lokaliseren van het knooppunt dat moet worden verwijderd en vervolgens het geheugen vrijmaken.
Hiervoor behouden we twee extra pointers curr en prev en doorlopen we de lijst om het knooppunt te lokaliseren. Het gegeven knooppunt dat moet worden verwijderd, kan het eerste knooppunt, het laatste knooppunt of het knooppunt daartussenin zijn. Afhankelijk van de locatie stellen we de curr- en prev-wijzers in en verwijderen we vervolgens de curr-knoop.
Een grafische weergave van de verwijderingsoperatie wordt hieronder weergegeven.
Traversal
Traversal is een techniek om elk knooppunt te bezoeken. In lineair gelinkte lijsten, zoals enkelvoudig gelinkte lijsten en dubbel gelinkte lijsten, is doorlopen gemakkelijk omdat we elk knooppunt bezoeken en stoppen wanneer NULL wordt aangetroffen.
Dit is echter niet mogelijk in een circulaire gekoppelde lijst. In een cirkelvormige gekoppelde lijst beginnen we vanaf het volgende van het laatste knooppunt, dat het eerste knooppunt is, en doorlopen we elk knooppunt. We stoppen als we weer bij het eerste knooppunt komen.
Nu presenteren we een implementatie van de circulaire gekoppelde lijstbewerkingen met behulp van C ++ en Java. We hebben hier invoeg-, verwijder- en doorloopbewerkingen geïmplementeerd. Voor een duidelijk begrip hebben we de circulaire gekoppelde lijst afgebeeld als
Dus aan het laatste knooppunt 50 koppelen we opnieuw knooppunt 10 dat het eerste knooppunt is, waardoor het wordt aangeduid als een circulaire gekoppelde lijst.
Uitgang:
De gecreëerde circulaire gekoppelde lijst is als volgt:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Het knooppunt met gegevens 10 wordt uit de lijst verwijderd
Circulaire gekoppelde lijst na het verwijderen van 10 is als volgt:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
Vervolgens presenteren we een Java-implementatie voor de circulaire gekoppelde lijstbewerkingen.
Uitgang:
De gemaakte circulaire gekoppelde lijst is:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Na het verwijderen van 40 is de circulaire lijst:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Voordelen nadelen
Laten we enkele voor- en nadelen van de circulaire gekoppelde lijst bespreken.
Voordelen:
- We kunnen naar elk knooppunt gaan en vanaf elk knooppunt oversteken. We hoeven alleen maar te stoppen als we hetzelfde knooppunt opnieuw bezoeken.
- Aangezien het laatste knooppunt naar het eerste knooppunt wijst, is het slechts één stap om vanaf het laatste knooppunt naar het eerste knooppunt te gaan.
Nadelen:
- Het omkeren van een circulaire gekoppelde lijst is omslachtig.
- Omdat de knooppunten met elkaar zijn verbonden om een cirkel te vormen, is er geen juiste markering voor begin of einde van de lijst. Daarom is het moeilijk om het einde van de lijst of lusbesturing te vinden. Als er niet voor wordt gezorgd, kan een implementatie in een oneindige lus terechtkomen.
- We kunnen niet in één stap teruggaan naar het vorige knooppunt. We moeten de hele lijst vanaf het begin doorlopen.
Toepassingen van circulaire gekoppelde lijst
- Real-time toepassing van circulaire gekoppelde lijst kan een besturingssysteem voor meerdere programmering zijn waarin het meerdere programma's plant. Elk programma krijgt een speciale tijdstempel om uit te voeren, waarna de bronnen worden doorgegeven aan een ander programma. Dit gaat continu in een cyclus door. Deze weergave kan efficiënt worden bereikt met behulp van een circulaire gekoppelde lijst.
- Games die met meerdere spelers worden gespeeld, kunnen ook worden weergegeven met behulp van een circulaire gekoppelde lijst waarin elke speler een knooppunt is dat de kans krijgt om te spelen.
- We kunnen een circulaire gekoppelde lijst gebruiken om een circulaire wachtrij weer te geven. Door dit te doen, kunnen we de twee wijzers voor en achter verwijderen die worden gebruikt voor de wachtrij. In plaats daarvan kunnen we slechts één aanwijzer gebruiken.
Gevolgtrekking
Een circulaire gekoppelde lijst is een verzameling knooppunten waarin de knooppunten met elkaar zijn verbonden om een cirkel te vormen. Dit betekent dat in plaats van de volgende pointer van het laatste knooppunt op nul te zetten, deze is gekoppeld aan het eerste knooppunt.
Een circulaire gekoppelde lijst is handig bij het weergeven van structuren of activiteiten die keer op keer moeten worden herhaald na een bepaald tijdsinterval, zoals programma's in een multiprogrammeringsomgeving. Het is ook gunstig voor het ontwerpen van een ronde wachtrij.
Circulair gekoppelde lijsten ondersteunen verschillende bewerkingen, zoals invoegen, verwijderen en doorlopen. Daarom hebben we de bewerkingen in deze tutorial in detail bekeken.
In ons volgende onderwerp over datastructuren leren we over de datastructuur van de stack.
Kijk hier om AZ van C ++ trainingshandleidingen hier te zien.
Aanbevolen literatuur
- Gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Wachtrijgegevensstructuur in C ++ met illustratie
- Stapel gegevensstructuur in C ++ met illustratie
- Prioriteitswachtrijgegevensstructuur in C ++ met illustratie
- Top 15 beste gratis tools voor datamining: de meest uitgebreide lijst
- Inleiding tot gegevensstructuren in C ++
- 15 beste ETL-tools in 2021 (een complete bijgewerkte lijst)