Doppelt verknüpfte Listen und deren Implementierung in Python 3

Verknüpfte Listen sind eine lineare Methode zum Speichern von Daten. Es besteht aus Knoten, die Daten enthalten, sowie Zeigern, wie Sie zum nächsten Datenelement gelangen. Stellen Sie sich Knoten als Mitglied einer Kette vor. Jede Kette ist aufeinander angewiesen, um eine starke Bindung aufrechtzuerhalten. Wenn zum Beispiel der mittlere Link fehlt, schlägt alles danach fehl. Es ist keine vollständige Kette mehr! Wie wird dies in verknüpfte Listen übersetzt? Wenn einer der Zeiger fehlt oder falsch ist, können die restlichen Daten nicht mehr gelesen werden.

Keine gültige Kette! Dies würde eine verknüpfte Liste brechen!

Das Thema dieses Artikels ist jedoch eine vielseitigere Version von verknüpften Listen - die doppelt verknüpfte Liste. Im Vergleich zu einer regulären (oder einfach verknüpften) Liste enthält eine doppelt verknüpfte Liste einen weiteren Zeiger, der als vorherige bezeichnet wird. Wie Sie vielleicht erraten haben, kann der Knoten so erkennen, wo sich der vorherige Knoten befindet. Im Vergleich dazu müsste eine einzeln verknüpfte Liste die gesamte Liste erneut bis zum vorherigen Punkt durchlaufen, um zum selben Punkt zu gelangen.

Informationen zu einfach verknüpften Listen finden Sie im Artikel meines Klassenkameraden:

Wie bereits erwähnt, verweisen Knoten auf andere Speicherorte. Was bedeutet das? Im Gegensatz zu Arrays, die an zusammenhängenden Orten gespeichert sind, haben verknüpfte Listen einfach Zeiger. In der folgenden Abbildung weist jeder Speicherblock (rot) zwei Zeiger auf. Es greift auf diese Informationen zu, indem es auf den nächsten Zeiger (schwarz) blickt. Wenn der vorherige Block gesucht werden soll, wird der vorherige Zeiger (weiß) angezeigt.

Wie implementiert man also eine doppelt verknüpfte Liste? Hier erfahren Sie, wie Sie in Python 3 vorgehen

Fügen Sie Ihrer Knotenklasse einfach eine .prev hinzu. Jetzt können Sie mit der Implementierung beginnen!

Vorteile - Mit Python 3-Code!

Was sind einige der Vorteile einer doppelt verknüpften Liste gegenüber einer einfach verknüpften? Nun, mit einer doppelt verknüpften Liste können Sie sich zwischen Ihren Knoten hin und her bewegen. So wird das Einfügen zum Kinderspiel. Bei doppelt verknüpften Listen müssen Sie Ihre verknüpfte Liste nur zum gewünschten Knoten übergehen und dann den vorherigen Knoten aufrufen.

Nachteile

Verknüpfte Listen sind zwar großartig, aber keine Komplettlösung. Wie bei vielen Datenstrukturen und Algorithmen sollte dies ein Werkzeug in Ihrem Arsenal sein. Einer der Nachteile gegenüber einer einfach verknüpften Liste besteht darin, dass mehr Speicher verbraucht wird, da jeder Link in einer doppelt verknüpften Liste den vorherigen Zeiger verfolgen muss. Außerdem ist es schwierig, den Zeiger im Auge zu behalten.

Ich bin derzeit noch dabei, die Umsetzung dieser Richtlinien zu üben. Dies ist meine zweite erfolgreiche Implementierung seit dem Schreiben dieses Artikels (April 2019). Jedes Mal wird es etwas einfacher, aber ich muss immer noch Diagramme zeichnen, wie der vorherige Zeiger mit all meinen anderen Funktionen interagiert.

Aber wofür würde das verwendet werden?

Ich höre dich fragen. Überlegen Sie, wann immer Sie ein vorheriges und nächstes Mal gesehen haben. Es gibt einige offensichtliche und subtile Möglichkeiten, wie sie implementiert werden können.

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

Was ist mit einem Fall wie einem Musikplayer? Es hat eine sehr explizite nächste und vorherige Schaltfläche. Eine doppelt verknüpfte Liste könnte verwendet werden, um zwischen diesen beiden Liedern zu wechseln.

Oder was ist mit einem Browser? Diese haben auch explizite Möglichkeiten, zwischen den von Ihnen besuchten Webseiten vor- und zurückzublättern.

Denken Sie jetzt an die gewünschte Textverarbeitungssoftware oder Bildbearbeitungssoftware. Immer wenn Sie einen Fehler machen, können Sie STRG (CMD für Mac) + Z drücken, um die letzte Aktion rückgängig zu machen. Ebenso können Sie mit STRG (CMD für Mac) + Y wiederholen, was Sie rückgängig gemacht haben. Warum kommt Ihnen das jetzt bekannt vor? Es könnte auch mit einer doppelt verknüpften Liste implementiert werden! Der vorherige Zeiger zeigt auf Aktionen, die ausgeführt wurden, während die Aktionen wiederholt werden können, wenn Sie zu viel rückgängig machen.

Quelle: https://gfycat.com/brilliantbeautifuldassieQuelle: https://www.solitairecardgames.com/spielanleitung-solitaire

Eine weniger offensichtliche Implementierung, an die ich dachte, war im Spiel Solitaire. Nebenstehend finden Sie ein Bild von Solitaire-Terminologien, um meinen Standpunkt zu verdeutlichen.

Das Spiel ist ein leuchtendes Beispiel, bei dem Sie ständig in der Lage sein müssen, die vorherigen und nächsten Karten anzuzeigen, egal ob diese auf dem Tableau oder auf dem Abfallstapel liegen. Wenn Sie eine Karte vom Abfallstapel auf das Tableau legen, wird der Abfallstapel mit der vorherigen Karte aktualisiert.

Für eine lebhaftere Diskussion der Verwendung von doppelt verknüpften Listen empfehle ich, die folgende Diskussion zum Stackoverflow zu lesen:

Wenn Sie also das nächste Mal eine verknüpfte Liste implementieren, versuchen Sie es mit einer doppelt verknüpften Liste. Es ist nicht viel mehr Code auf einer verknüpften Liste und es gibt tiefgreifende Vorteile!

Zusätzliche Ressourcen

Einen vollständigen Link zu meiner Python 3-Implementierung einer doppelt verknüpften Liste finden Sie auf meinem Github-Repo.

Wenn Sie eine 3D-druckbare Kette von doppelt verknüpften Listen möchten, habe ich sie zu Thingiverse hochgeladen.

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