What is a Doubly Linked List?

Eine doppelt verkettete Liste ist eine Sequenz von Knoten, bei der jeder Knoten einen Wert und zwei Zeiger trägt: prev zum vorherigen Knoten und next zum nächsten Knoten. Die Liste selbst behält beide Enden im Blick, den head (erster Knoten) und den tail (letzter Knoten).

Die zwei Zeiger pro Knoten und die zusätzliche tail-Referenz bringen uns viele Vorteile. Das Hinzufügen am Ende ist nun O(1) (direkter Sprung zu tail, anstatt die Kette zu durchlaufen), und das Entfernen des letzten Knotens ist ebenfalls O(1) (da wir den vorletzten Knoten über tail.prev erreichen können). Der Nachteil ist ein höherer Speicherverbrauch pro Knoten sowie mehr Zeiger, die bei jedem Einfügen und Entfernen synchron gehalten werden müssen.

Die fünf Hauptoperationen einer doppelt verketteten Liste sind:

1. AddFirst: Fügt einen Wert am Anfang der Liste hinzu.
2. AddLast: Fügt einen Wert am Ende der Liste hinzu (O(1)!).
3. Get: Gibt den Wert an einem bestimmten Index zurück.
4. RemoveLast: Löscht den letzten Knoten (O(1)!).
5. Size: Gibt die Anzahl der aktuell gespeicherten Knoten zurück.

Erstellen wir zuerst eine Node-Klasse und bauen darauf die DoublyLinkedList auf!