Vorlesung Informatik 2 - Teil B: Theorie

3.4 Doppelt verkettete Liste

Stack und Queue haben wir als einfach verkettete Liste implementiert.

Man kann eine Liste auch so konstruieren, dass ihre Einträge doppelt verkettet sind:

------------------------------
|  pre  |  inhalt   |  post | Eintrag in eine doppelt verkettete Liste
------------------------------

In Java schreibt man wieder eine innerer Klasse Eintrag:

class VerketteteListe<T>
      private class Eintrag{
            T inhalt;
            Eintrag pre, post;
     }
     private Eintrag anfang;
      ...
}

     

pre und post sind Zeiger auf den Vorgänger und den Nachfolger. In dieser Liste kann man vorwärts und rückwärts zum jeweils nächsten Element springen. 

Das Löschen oder Einfügen eines Elements hat die Komplexität O(1), während es beim Array die Komplexität O(N) haben, da ja ein Bereich des Arrays verschoben werden muss.

Allerdings hat der Zugriff auf ein Beliebiges Element die Komplexität O(N), da man erst an die gewünschte Stelle gehen muss, während beim Array diese Operation die Komplexität O(1) hat.

Es hängt also von der jeweiligen Anwendung ab ob man eine Array-basierte Liste (java.util.Vector) oder eine verkettete Liste (java.util.LinkedList) verwendet.

Lehrvideo  (YouTube) 

Und hier noch der ultimative Hintergrund zu verketteten Listen: