Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Doppelt verkettete Listen

Doppelt verkettete Liste

Wir haben nun gesehen, dass die oben behandelten elementaren Operationen auf einer einfach verketten Liste einen hohen Rechenaufwand aufweisen. Nehmen wir beispielweise an, wir wollten eine einfach verkette Liste sortieren. Wir haben bisher gesehen, dass wir in jedem Einzelschritt jedes Sortierverfahrens, je zwei Elemente vertauschen. Es ist also interessant das Laufzeitverhalten der einfach verketteten Liste für den Tausch zweier Elemente zu untersuchen. Nehmen wir an, wir hätten zwei Zeiger auf die Elemente in der Liste, welche wir vertauschen wollen. Wir benötigen jedoch die jeweiligen Vorgänger der Elemente um deren Nachfolgerzeiger verbiegen zu können. Diese Situation ist in der folgenden Abbildung dargestellt.

Vertauschen zweier Elemente (x und y) in einer einfach verketteten Liste

Hierdurch entsteht ein erheblicher Laufzeitaufwand, da wir die Liste vom Kopf angefangen bis zu den jeweiligen Vorgängerelementen durchlaufen müssen. Es entsteht daher ein Aufwand $O(n)$. Eine Lösung bietet hier die doppelt verkettete Liste. Jedes Element der doppelt verketteten Listen enhält zusätzlich zu dem von der einfach verketteten Liste bereits bekannten Nachfolgerzeiger next auch einen Zeiger auf den Vorgänger prev. Durch die Verfügbarkeit eines Zeiger auf das vorausgehende Element können wir nun in konstanter Zeit zwei Elemente tauschen. Mehr hierzu werden wir in den Übungsaufgaben besprechen. Die folgende Abbildung zeigt ein Beispiel einer doppelt verketteten Liste.

Beispiel einer doppelt verketteten Liste.

insertionSort

Es gibt Anwendungsfälle in denen sortiere Listen verwendet werden. Sortieren ist eine der Informatik häufig zu lösende Aufgabe. Wir haben bereits einige Verfahren zum Sortieren von Arrays kennen gelernt. Arrays haben jedoch den Nachteil, dass sie eine festgelegte Größe besitzen und eine Änderung der Größe ein Umkopieren des Arrays erfordert, welches einen hohen Rechenaufwand mit sich bringt. Daher möchte man auch eine Liste sortieren können. Hierzu bietet sich InsertionSort als geeignetes Verfahren an. Man fügt einfach jedes Element an der richtigen Stelle ein. Man beginnt demnach mit einer leeren Liste. Anschließend fügt man die Elemente nacheinander jeweils richtig ein. In einem Array wäre dieses Verfahren schwer Praktikabel weil das Einfügen zwischen zwei vorhandenen Elementen eine erheblichen Kopieraufwand zum Verschieben der bereits vorhandenen Elemente mit sich brächte. In der folgenden Abbildung sehen wir eine sortierte Liste mit den Einträgen 5, 9, 12 und 17. In diese Liste wollen wir die Zahl 13 einfügen.

Sortieren durch Einfügen

Hierzu müssen wir den Knoten in der Liste mit dem größten Wert, welcher gerade noch kleiner ist als 13 finden und anschließend die Zeiger entsprechend verbiegen. Der zu entfernende Zeiger ist in der Abbildung als gepunktete Linie angedeutet. Die neu einzufügenden Zeiger sind als gestrichelte Linien dargestellt. Bei diesem Verfahren haben wir immer eine sortierte Liste. Bei jedem Einfügevorgang wird darauf geachtet, dass die Sortiertheit der Liste erhalten bleibt. In der Java Collection API gibt es die Klasse SortedList, welche genau dieses Verfahren implementiert. Schauen wir uns nun die Implementierung des Verfahrens an.

insertSorted(x, L)
  if isEmpty(L)
    insert(x, L)
  else
    while tmp.next ≠ null and tmp.next.data < x
      tmp := tmp.next
    node := new(x)
    node.next := tmp.next
    tmp.next := node