doppelt verkettete Listen

• Soll eine Folge in beiden Richtungen effizient abgelaufen werden können, so ist eine Doppelverzeigerung erforderlich.

Implementierungsvarianten

• Kopfzeiger ohne Nullelement, ohne Zyklus
  !introprog-v04-listen, p.149
• Kopfzeiger auf Nullelement, zyklisch verkettet
  !introprog-v04-listen, p.149

Merkmale:

• Teilweise schnellere Laufzeit, z.B. wenn Pointer auf Listenposition vorhanden: delete, insert in O(1)
• Durchlaufrichtung frei wählbar (invertieren nicht notwendig)
• Aber: Erhöhter Speicherbedarf für Sekundärdaten • Nachfolger und Vorgänger, d.h., next und previous Pointer