Am 14. September 2017 haben wir eine überarbeitete Fassung unserer Datenschutzrichtlinie veröffentlicht. Wenn Sie video2brain.com weiterhin nutzen, erklären Sie sich mit diesem überarbeiteten Dokument einverstanden. Bitte lesen Sie es deshalb sorgfältig durch.

Grundlagen der Programmierung: Datenstrukturen

Einfach und doppelt verlinkte Listen

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Bei doppelt verlinkten Listen hat jedes Element zwei Zusatzinformationen: einen Link auf das vorhergehende Element und einen auf das nächste Element.

Transkript

Wir haben mit der Idee einer Liste angefangen. Also mit der Idee einer geordneten Reihe von Elementen und haben dann verlinkte Listen angesehen. Denn die sind eine sehr gängige Art der Implementierung von Listen. Wir haben uns angesehen, dass die Reihenfolge dadurch erreicht wird, dass jeder Knoten eine Verlinkung zum nächsten Knoten aufweist. Das ist eine verlinkte Liste. Um jetzt aber etwas spezifischer zu werden, das ist eine einfach verlinkte Liste, wo wir eine einfache Verlinkung nach vorne in jedem Knoten haben. Sie können aber genau so eine doppelt verlinkte Liste haben. Der Unterschied liegt in einem zusätzlichen Stück Information. Anstatt, dass jeder Knoten nur eine Verlinkung zum nächsten Knoten hat, hat er nun genau so eine Referenz zum vorigen Knoten. Das Ganze optisch darzustellen kann jetzt etwas beängstigend wirken, denn ich zeige hier auch die Idee, dass diese Objekte an beliebiger Stelle im Speicher liegen können. Sie müssen nicht nebeneinander liegen. Aber jedes Objekt hat zwei Informationen. Eine Referenz zum nächsten Objekt und eine zum vorherigen Objekt. Das ist nun eine doppelt verlinkte Liste. Sie erlaubt uns vorwärts und rückwärts zu gehen, um die Liste in beide Richtungen durchlaufen zu können. Das mag auf den ersten Blick nicht besonders sinnvoll sein, aber es macht einige Operationen etwas leichter. Zum Beispiel, wenn wir die Inhalte aus der Mitte der Liste entfernen wollen. Mit einer doppelt verlinkten Liste habe ich eine Referenz in beide Richtungen. Zum vorhergehenden und zum nächsten Knoten. Es ist supereinfach, Veränderungen durchzuführen. Entfernen und Einfügen bei doppelt verlinkten Listen: ebenfalls super einfach. Eine Frage könnte sein, was wir mit dem ersten und letzten Knoten machen sollen. Es war bereits von der Idee die Rede, dass der letzte Knoten, in unserem Fall Objekt fünf, seinen nächsten Link entweder auf eine leere Referenz setzt mit dem Hintergedanken, dass da nichts mehr ist, zu dem man gehen könnte, oder er könnte auf einen Terminator oder Wächterknoten verweisen, um deutlich zu machen, dass hier Schluss ist. Bei der doppelt verlinkten Liste ist es genau das, was Sie auch beim ersten Knoten beim Verweis auf einen vorigen Knoten machen. Der verweist dann ebenfalls auf diesen Wächter beziehungsweise Terminator. Wie auch immer. Es gibt noch eine weitere Möglichkeit. Anstatt die Start- und Endknoten auf einen Terminator verweisen zu lassen, können Sie statt dessen beim ersten Knoten direkt auf den letzten verweisen, und umgekehrt. Das würde als 'im Kreis laufende Verlinkung' angesehen werden. Oder eben 'kreisförmig doppelt verlinkte Liste'. Wenn wir am Ende der Liste angelangt sind und zum nächsten Eintrag wollen, fangen wir einfach wieder von vorne an. Wir haben also eine einfach verlinkte Liste, eine doppelt verlinkte Liste, und eben eine kreisförmig verlinkte Liste.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!