Dubbel gekoppelde lijsten en hoe ze te implementeren in Python 3

Gekoppelde lijsten zijn een lineaire manier om gegevens op te slaan. Het bestaat uit knooppunten die gegevens bevatten en aanwijzingen voor het bereiken van het volgende gegeven. Denk aan knooppunten als lid van een ketting. Elke ketting is van elkaar afhankelijk om een ​​sterke band te behouden. Als de middelste link bijvoorbeeld alles mist nadat dat is mislukt. Het is niet langer een complete keten! Hoe vertaalt dit zich naar gekoppelde lijsten? Als een van de verwijzingen ontbreekt of onjuist is, kan de rest van de gegevens niet meer worden gelezen.

Geen geldige ketting! Dit zou een gekoppelde lijst verbreken!

Het onderwerp van dit artikel is echter een veelzijdiger versie van gekoppelde lijsten - de dubbel gekoppelde lijst. In vergelijking met een gewone (of afzonderlijk) gekoppelde lijst, bevat een dubbel gekoppelde lijst een andere aanwijzer genaamd vorige. Zoals je misschien wel raadt, kan de knoop weten waar de vorige knoop is. Ter vergelijking: een afzonderlijk gekoppelde lijst zou de hele lijst opnieuw moeten doorlopen naar het punt ervoor om hetzelfde punt te bereiken.

Raadpleeg het artikel van mijn klasgenoot voor informatie over lijsten met afzonderlijke links:

Zoals eerder vermeld, wijzen knooppunten naar andere locaties in het geheugen. Wat betekent dat? Welnu, in tegenstelling tot arrays die op aaneengesloten locaties worden opgeslagen, hebben gekoppelde lijsten eenvoudigweg verwijzingen. In het onderstaande diagram heeft elk geheugenblok (rood) twee wijzers die ernaar verwijzen. Het geeft toegang tot die informatie door naar de volgende aanwijzer (zwart) te kijken. Als het het vorige blok wil vinden, kijkt het naar de vorige aanwijzer (wit).

Dus hoe implementeer je een dubbel gekoppelde lijst? Zo gaat het in Python 3

Voeg eenvoudig een .prev toe aan uw Node-klasse. Nu ben je klaar om te beginnen met implementeren!

Voordelen - Met Python 3-code!

Wat zijn enkele voordelen van een dubbel gekoppelde lijst boven een enkel gekoppelde lijst? Welnu, met een dubbel gekoppelde lijst kunt u achteruit en vooruit schakelen tussen uw knooppunten. Dit maakt dingen zoals invoegen heel eenvoudig. Met dubbel gekoppelde lijsten doorloopt u gewoon uw gekoppelde lijst naar het gewenste knooppunt en roept u vervolgens het vorige knooppunt aan.

Nadelen

Hoewel er geweldige dingen zijn aan gelinkte lijsten, is dit geen alles-in-één oplossing. Zoals met veel datastructuren en algoritmen zou dit een hulpmiddel in je arsenaal moeten zijn. Een van de nadelen van een afzonderlijk gekoppelde lijst is dat er meer geheugenverbruik is omdat elke koppeling in een dubbel gekoppelde lijst die vorige aanwijzer moet bijhouden. Bovendien is het moeilijk om deze aanwijzer bij te houden.

Ik ben eigenlijk nog steeds bezig met het oefenen van de implementatie ervan. Dit zal mijn tweede succesvolle implementatie zijn geweest bij het schrijven van dit artikel (april 2019). Elke keer wordt het iets eenvoudiger, maar ik moet nog steeds diagrammen tekenen van de interactie van de vorige aanwijzer met al mijn andere functies.

Maar waar zou dit voor worden gebruikt?

Ik hoor je vragen. Denk aan elk moment dat je een vorige en volgende hebt gezien. Er zijn enkele voor de hand liggende en subtiele manieren waarop ze kunnen worden geïmplementeerd.

Bron: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

Hoe zit het in een geval als een muziekspeler? Het heeft een zeer expliciete volgende en vorige knop. Een dubbel gekoppelde lijst kan worden gebruikt om tussen die twee nummers te wisselen.

Of wat dacht u van een browser? Deze hebben ook expliciete manieren om heen en weer te gaan tussen webpagina's die u hebt bezocht.

Denk nu eens na over uw tekstverwerkingssoftware of foto-editor naar keuze. Telkens wanneer u een fout maakt, kunt u op CTRL (CMD voor Mac) + Z drukken om die laatste actie ongedaan te maken. Evenzo kun je opnieuw doen wat je ongedaan hebt gemaakt met CTRL (CMD voor Mac) + Y. Waarom komt dit nu bekend voor? Het kan ook worden geïmplementeerd met een dubbel gekoppelde lijst! De vorige aanwijzer verwijst naar acties die zijn uitgevoerd en kan de acties ook opnieuw uitvoeren als u te veel ongedaan maakt.

Bron: https://gfycat.com/brilliantbeautifuldassieBron: https://www.solitairecardgames.com/how-to-play-solitaire

Een minder voor de hand liggende implementatie waar ik aan dacht was in het spel Solitaire. Aan de zijkant staat een afbeelding van Solitaire-terminologieën om mijn punt te illustreren.

Het spel is een lichtend voorbeeld waarbij je constant de vorige en volgende kaarten moet kunnen bekijken, of dat nu op het tableau of op de afvalstapel is. Terwijl u een kaart van de afvalstapel naar het tableau speelt, wordt de afvalstapel bijgewerkt met de kaart ervoor.

Voor een meer levendige discussie over het gebruik op dubbel gekoppelde lijsten raad ik aan deze discussie over stackoverflow te bekijken:

Dus waarom zou u de volgende keer dat u een gekoppelde lijst implementeert, geen dubbel gekoppelde lijst proberen? Het is niet zo veel meer code bovenaan een gekoppelde lijst en er zijn grote voordelen!

Aanvullende bronnen

Een volledige link naar mijn Python 3-implementatie van een dubbel gekoppelde lijst is te vinden op mijn Github-repo.

Als je een 3D-printbare keten van dubbel gekoppelde lijsten wilt, heb ik deze geüpload naar Thingiverse.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ