MyWiki

Double Linked List

Statt eines großen Speicherebereichs in dem sich die Pointer auf die Elemente/Objekte hintereinander befinden (so wie das List macht) wird eine Kette benutzt und die Speicherbereiche der Pointer können irgendwo im Speicher liegen.
Neben dem Pointer auf das eigentliche Objekt wird ein Pointer auf das Element vor dem jeweiligen in der „Liste“ und einer auf das nächste Element in der „Liste“ gespeichert.
Dadurch kann von einem Eintrag aus problemlos zum vorhergehenden oder nachfolgenden gesprungen werden.

Praktisch stimmt das obige wohl nur in der Theorie, in der Praxis (CPython) reserviert Python Speicherblöcke und speichert darin immer einen Satz von Pointern. Ist der Block voll alloziert es den nächsten Speicherblock und verweist zwischen diesen Speicherblöcken per Double Links aufeinander, aber nicht innerhalb des Blocks.
Das heißt in CPython ist deque eigentlich ein Hybrid aus Liste und double linked list.

Vorteile (gegenüber List):

• Einfügeoperation (insert) sind schneller (O(1) vs (O(n))
  • da bei List die Pointer alle nacheinander liegen müssen beim Einfügen alle nachfolgenden Pointer um 1 nach Rechts verschoben werden im Speicher
  • deque hingegen kann einfach beim vorhergehenden Element den Nachfolge-Pointer und beim nachfolgenden Element den Vorgänger-Pointer auf das neu eingefügte Element ändern
• remove-Operationen sind schneller (O(1) vs O(1)), Grund siehe bei Einfügeoperationen
• append und pop können schneller sein
  • Speicher in CPython ist in Blöcken organisiert → es wird immer eine bestimmte Anzahl Blöck für eine Datenstruktur reserviert
  • Lists benötigen zusammenhängende Blöcke (da die Daten hintereinander weg abgelegt werden)
    • ist ein Block voll muss ein anschließender Block reserviert werden
      • ist der nachfolgende Block bereits belegt müssen mehrere neue hintereinander liegende Blöcke reserviert werden die frei sind
      • anschließend müssen alle bestehenden Daten in die neuen Blöcke kopiert werden
  • Deque benutzt ebenfalls Blöcke in denen Daten hintereinander abgelegt sind
    • aber die Blöcke untereinander verweisen per Double Links (jeder Block kennt seinen Vorgänger und seinen Nachfolger) aufeinander → die Blöcke müssen also nicht hintereinander im Speicher liegen
    • die Daten müssen nicht kopiert werden, es werden einfach weitere Blöcke reserviert
• geringere Speicher-Fragmentierung/weniger Speicherbedarf?
  • Listen benötigen zusammenhängende Speicherbereiche, deque kann verteilte Blöcke nutzen
  • wenn die Liste also groß ist und das Programm eine Weile läuft ist der Speicher vermutlich fragmentiert, es gibt in CPython wenig zusammenhängende große Speicherbereiche, das heißt es muss neuer Speicherbereich vom System genommen werden
  • deque kann vermutlich einfach verteilte Blöcke die frei sind wieder recyclen → der Gesamtspeicherbedarf steigt nicht

Nachteile (gegenüber List):

• Zugriff per Index ist langsamer
  • bei Lists liegen die Pointer hintereinander im Speicher, Pointer haben eine feste Größe
    • List muss nur wissen bei welcher Speicheradresse die Liste beginnt und wie groß ein Eintrag in der Liste (Pointer-Adresse ist) um den entsprechenden Eintrag anhand des Index zu finden
      • Startadresse + Eintraggröße*Index-Nummer = Zieladresse
  • bei deque liegen die Daten bis zur Größe eines Blocks hintereinander, aber sobald Block-Grenzen im Speichermanagement überschritten werden, müssen alle Blöcke bis zum Ziel durchlaufen werden um jeweils den nachfolgenden Block zu finden (es kann nicht einfach gesprungen werden, da die Adressen an denen die Blöcke liegen nicht bekannt sind)
• Verbraucht mehr Speicher
  • da zusätzlich die Vorgänger- und Nachfolge-Adressen in den Blöcken gespeichert werden muss