Menu

Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie

  • Hoofd
  • Andere
  • Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie

doubly linked list data structure c with illustration

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Een diepgaande zelfstudie over dubbel gekoppelde lijst.

Een dubbel gelinkte lijst is een variatie op de enkelvoudig gelinkte lijst. We zijn ons ervan bewust dat de enkelvoudig gekoppelde lijst een verzameling knooppunten is waarbij elk knooppunt een datagedeelte heeft en een aanwijzer die naar het volgende knooppunt wijst.

Een dubbelgekoppelde lijst is ook een verzameling knooppunten. Elk knooppunt bestaat hier uit een datagedeelte en twee pointers. Een aanwijzer wijst naar het vorige knooppunt terwijl de tweede aanwijzer naar het volgende knooppunt wijst.

​ Bekijk hier de diepgaande C ++ trainingshandleidingen.

DUBBEL GEKOPPELDE LIJST

Wat je leert:

Dubbel gekoppeld in C ++

Net als in de enkelvoudig gelinkte lijst heeft ook de dubbel gelinkte lijst een kop en een staart. De vorige wijzer van de kop is ingesteld op NULL omdat dit het eerste knooppunt is. De volgende pointer van het staartknooppunt is ingesteld op NULL omdat dit het laatste knooppunt is.

Een basislay-out van de dubbel gelinkte lijst wordt getoond in het onderstaande diagram.

Een basislay-out van de dubbel gelinkte lijst

In de bovenstaande afbeelding zien we dat elk knooppunt twee aanwijzers heeft, een wijst naar het vorige knooppunt en de andere wijst naar het volgende knooppunt. Alleen het eerste knooppunt (kop) heeft het vorige knooppunt ingesteld op nul en het laatste knooppunt (staart) heeft de volgende aanwijzer ingesteld op nul.

Omdat de dubbel gelinkte lijst twee aanwijzingen bevat, d.w.z. vorige en volgende, kunnen we deze in de richtingen vooruit en achteruit verplaatsen. Dit is het belangrijkste voordeel van een dubbel gelinkte lijst ten opzichte van de enkelvoudig gelinkte lijst.

top gratis youtube naar mp3 converter

Verklaring

In C-stijl declaratie wordt een knooppunt van de dubbel gelinkte lijst als volgt weergegeven:

​

Afgezien van de bovenstaande verklaring, kunnen we ook een knooppunt in de dubbel gelinkte lijst vertegenwoordigen als een klasse in C ++. Een dubbel gelinkte lijst wordt weergegeven als een klasse wanneer we STL gebruiken in C ++. We kunnen ook een dubbel gelinkte lijst implementeren met behulp van een klasse in Java.

Basisbewerkingen

Hieronder volgen enkele van de bewerkingen die we kunnen uitvoeren op een dubbel gelinkte lijst.

Invoeging

Invoegbewerking van de dubbel gekoppelde lijst voegt een nieuw knooppunt in de gekoppelde lijst in. Afhankelijk van de positie waar het nieuwe knooppunt moet worden ingevoegd, kunnen we de volgende invoegbewerkingen uitvoeren.

  • Insteek voor - Voegt een nieuw knooppunt in als het eerste knooppunt.
  • Inbrengen aan het einde - Voegt aan het einde een nieuw knooppunt in als het laatste knooppunt.
  • Invoegen voor een knoop - Gegeven een knoop voegt een nieuw knooppunt in voor dit knooppunt.
  • Invoegen na een knoop - Gegeven een knoop voegt een nieuw knooppunt in na dit knooppunt.

Verwijdering

Met een verwijderingsoperatie wordt een knooppunt verwijderd van een bepaalde positie in de dubbelgekoppelde lijst.

  • Verwijderen van het eerste knooppunt - Verwijdert het eerste knooppunt in de lijst
  • Verwijderen van het laatste knooppunt - Verwijdert het laatste knooppunt in de lijst.
  • Verwijdering van een knoop gezien de gegevens - Gegeven de gegevens, koppelt de bewerking de gegevens aan de knooppuntgegevens in de gekoppelde lijst en wordt dat knooppunt verwijderd.

Traversal

Traversal is een techniek om elk knooppunt in de gekoppelde lijst te bezoeken. In een dubbel gelinkte lijst hebben we twee soorten traversals, aangezien we twee wijzers hebben met verschillende richtingen in de dubbel gelinkte lijst.

  • Voorwaartse verplaatsing - De verplaatsing wordt gedaan met behulp van de volgende wijzer die in voorwaartse richting is.
  • Achterwaartse verplaatsing - Traversal wordt gedaan met behulp van de vorige aanwijzer die de achterwaartse richting is.

Omgekeerde

Deze bewerking keert de knooppunten in de dubbelgekoppelde lijst om, zodat het eerste knooppunt het laatste knooppunt wordt en het laatste knooppunt het eerste knooppunt.

Zoeken

De zoekbewerking in de dubbelgekoppelde lijst wordt gebruikt om naar een bepaald knooppunt in de gekoppelde lijst te zoeken. Voor dit doel moeten we de lijst doorlopen totdat er overeenkomende gegevens zijn gevonden.

Invoeging

Plaats een knoop aan de voorkant

Plaats een knoop aan de voorkant

Het invoegen van een nieuw knooppunt vooraan in de lijst wordt hierboven weergegeven. Zoals te zien is, is het vorige nieuwe knooppunt N ingesteld op nul. Hoofd wijst naar het nieuwe knooppunt. De volgende wijzer van N wijst nu naar N1 en de vorige van N1 die eerder naar Null wees, wijst nu naar N.

Voeg aan het einde een knoop in

Voeg aan het einde een knoop in

Het invoegen van een knoop aan het einde van de dubbelgekoppelde lijst wordt bereikt door de volgende pointer van nieuwe knoop N naar nul te wijzen. De vorige wijzer van N verwijst naar N5. De ‘Volgende’ wijzer van N5 wordt naar N.

Voeg een knoop in voor / na het gegeven knooppunt

Voeg knooppunt in voor-na gegeven knooppunt

Zoals getoond in het bovenstaande diagram, veranderen we, wanneer we een knooppunt vóór of na een bepaald knooppunt moeten toevoegen, de vorige en volgende verwijzingen van de voor en na knooppunten om op de juiste manier naar het nieuwe knooppunt te wijzen. Ook worden de nieuwe knooppuntaanwijzers op de juiste manier naar de bestaande knooppunten verwezen.

Het volgende C ++ -programma demonstreert alle bovenstaande methoden om knooppunten in de dubbel gekoppelde lijst in te voegen.

​

Uitgang:

De dubbel gelinkte lijst is als volgt:

1020304050 NULL

Het bovenstaande programma construeert een dubbelgekoppelde lijst door de knooppunten in te voegen met behulp van drie invoegmethoden, d.w.z. het knooppunt aan de voorkant invoegen, het knooppunt aan het einde invoegen en het knooppunt na het gegeven knooppunt invoegen.

Vervolgens demonstreren we dezelfde werking als een Java-implementatie.

​

Uitgang:

Dubbel gelinkte lijst gemaakt is als volgt:

beste videogamebedrijven om voor 2018 te werken

1020304050null

Verwijdering

Een knooppunt kan worden verwijderd uit een dubbel gelinkte lijst vanaf elke positie, zoals vanaf de voorkant, het einde of elke andere gegeven positie of gegeven gegevens.

Bij het verwijderen van een knooppunt uit de dubbelgekoppelde lijst, verplaatsen we eerst de pointer die naar dat specifieke knooppunt wijst, zodat de vorige en volgende knooppunten geen enkele verbinding hebben met het te verwijderen knooppunt. We kunnen het knooppunt dan gemakkelijk verwijderen.

Beschouw de volgende dubbel gelinkte lijst met drie knooppunten A, B, C.Laten we bedenken dat we knooppunt B moeten verwijderen.

dubbel gekoppelde lijst met drie knooppunten A, B, C

Zoals te zien is in de bovenstaande reeks van het diagram, hebben we aangetoond dat knooppunt B uit de gegeven gekoppelde lijst wordt verwijderd. De volgorde van de bewerking blijft hetzelfde, zelfs als het knooppunt de eerste of de laatste is. De enige zorg die moet worden genomen, is dat als in het geval dat het eerste knooppunt wordt verwijderd, de vorige aanwijzer van het tweede knooppunt op nul wordt gezet.

Evenzo, wanneer het laatste knooppunt wordt verwijderd, wordt de volgende aanwijzer van het vorige knooppunt op nul gezet. Als tussenliggende knooppunten worden verwijderd, is de volgorde zoals hierboven.

We verlaten het programma om een ​​knooppunt uit een dubbel gelinkte lijst te verwijderen. Merk op dat de implementatie in de lijn van de invoegimplementatie zal zijn.

Keer dubbel gekoppelde lijst om

Het omkeren van een dubbel gelinkte lijst is een belangrijke operatie. Hierin wisselen we eenvoudig de vorige en volgende wijzers van alle knooppunten en ook de kop- en staartwijzers.

Hieronder is een dubbel gelinkte lijst weergegeven:

Keer dubbel gelinkte lijst om

De volgende C ++ -implementatie toont de Reverse Doubly Linked List.

​

Uitgang:

Originele dubbel gelinkte lijst:

1 2 3 4 5

Dubbel gelinkte lijst omkeren:

5 4 3 2 1

Hier wisselen we de linker en rechter wijzers om en verplaatsen ze naar elkaar toe totdat ze elkaar ontmoeten of kruisen. Vervolgens worden de eerste en laatste knooppunten verwisseld.

Het volgende programma is de Java-implementatie voor het omkeren van een dubbel gelinkte lijst. In dit programma maken we ook gebruik van het verwisselen van de linker- en rechterknooppunten zoals we deden in ons vorige programma.

​

Uitgang:

Originele dubbel gelinkte lijst:

1 2 3 4 5

Omgekeerde dubbel gelinkte lijst:

5 4 3 2 1

Voordelen / nadelen ten opzichte van een enkelvoudig gekoppelde lijst

Laten we enkele van de voor- en nadelen bespreken van een dubbel gelinkte lijst ten opzichte van de enkelvoudig gelinkte lijst.

Voordelen:

  • De dubbel gekoppelde lijst kan zowel in voorwaartse als achterwaartse richting worden doorlopen, in tegenstelling tot enkel gekoppelde lijsten die alleen in voorwaartse richting kunnen worden doorlopen.
  • De verwijderingsoperatie in een dubbelgekoppelde lijst is efficiënter in vergelijking met een enkelvoudige lijst wanneer een bepaald knooppunt is opgegeven. Omdat we in een enkelvoudig gekoppelde lijst een vorig knooppunt nodig hebben om het gegeven knooppunt te verwijderen, moeten we soms de lijst doorlopen om het vorige knooppunt te vinden. Dit raakt de uitvoering.
  • Invoegbewerking kan eenvoudig worden uitgevoerd in een dubbel gelinkte lijst in vergelijking met de enkelvoudig gelinkte lijst.

Nadelen:

  • Omdat de dubbel gelinkte lijst nog een extra pointer bevat, d.w.z. vorige, is de geheugenruimte die wordt ingenomen door de dubbel gelinkte lijst groter in vergelijking met de enkelvoudig gelinkte lijst.
  • Aangezien er twee aanwijzingen aanwezig zijn, d.w.z. vorige en volgende, moeten alle bewerkingen die op de dubbel gekoppelde lijst worden uitgevoerd, voor deze aanwijzingen zorgen en ze onderhouden, wat resulteert in een knelpunt in de prestaties.

Toepassingen van dubbel gekoppelde lijst

Een dubbel gelinkte lijst kan worden toegepast in verschillende real-life scenario's en toepassingen, zoals hieronder besproken.

  • Een kaartspel in een spel is een klassiek voorbeeld van een dubbel gelinkte lijst. Aangezien elke kaart in een stapel de vorige kaart en de volgende kaart opeenvolgend heeft, kan dit kaartspel gemakkelijk worden weergegeven met behulp van een dubbel gekoppelde lijst.
  • Browsergeschiedenis / cache - De browsercache heeft een verzameling URL's en kan worden genavigeerd met de knoppen vooruit en achteruit. Dit is een ander goed voorbeeld dat kan worden weergegeven als een dubbel gelinkte lijst.
  • De meest recent gebruikte (MRU) kan ook worden weergegeven als een dubbel gelinkte lijst.
  • Andere datastructuren zoals Stacks, hashtabel, de binaire boom kunnen ook worden geconstrueerd of geprogrammeerd met behulp van een dubbel gelinkte lijst.

Gevolgtrekking

Een dubbel gelinkte lijst is een variatie op de enkelvoudig gelinkte lijst. Het verschilt van de enkelvoudig gekoppelde lijst doordat elk knooppunt een extra aanwijzer bevat naar het vorige knooppunt, samen met de volgende aanwijzer.

Deze aanwezigheid van een extra aanwijzer vergemakkelijkt het invoegen en verwijderen van de dubbel gelinkte lijst, maar vereist tegelijkertijd extra geheugen om deze extra aanwijzers op te slaan.

Zoals reeds besproken, heeft de dubbel gelinkte lijst verschillende toepassingen in real-time scenario's zoals browsercache, MRU's, enz. We kunnen ook andere datastructuren weergeven zoals bomen, hashtabellen, enz. Met behulp van een dubbel gelinkte lijst.

In onze volgende tutorial zullen we meer leren over de circulaire gekoppelde lijst.

​ Lees hier de populaire C ++ trainingsserie.

Aanbevolen literatuur

^