Liste (Datenstruktur)

Die verkettete Liste ist eine dynamische Datenstruktur, die eine geordnete Speicherung von Datenelementen unterstützt. Die Anzahl der Objekte muss dabei nicht im Vorhinein (nicht bspw. zur Compile-Zeit) bekannt sein und bleibt für die gesamte Lebenszeit der Liste offen.

Einfach verkettete Listen

Der Datentyp L_A der einfach verketteten Listen mit Elementen vom Typ ist rekursiv definiert als $L=Nil|[A,L_{A}]$ . Die technische Realisierung erfolgt meistens durch einzelne Knoten, die aus den Nettodaten selbst und einem Verweis auf den Nachfolgeknoten besteht. Im letzten Knoten ist als Nachfolgeknoten der sogenannte Null-Zeiger angegeben, der auch $Nil$ heißt.^[1]

Elementare Listenoperationen sind das Erweitern der Liste um einen Knoten am Anfang und das Entfernen des ersten Knotens, die in der Zeit O(1) erfolgen können. Dadurch ist die natürlichste Anwendung einer verketteten Liste der nur durch den Speicherplatz begrenzte Stapelspeicher (oder Stack).

Einfach verkettete Liste mit drei Werten

Vorteile

Wenn das Suchen erledigt, der Einfügepunkt gefunden ist, ist der Aufwand fürs Einfügen an jeder Stelle , wogegen beim Array Datensätze umkopiert werden müssen.
Geringer zusätzlicher Speicherbedarf (1 Zeiger).

Nachteile

Die Kosten fürs Suchen sind , da ungünstigstenfalls über jeden Knoten iteriert werden muss.

Anwendungen

Einfach verkettete Listen werden in hochdynamischen Umgebungen verwendet, in denen mit Arrays nicht mehr sinnvoll gearbeitet werden kann, da diese den Umgang mit syntaktischen Operationen enorm erschweren. So ist die einfach verkettete Liste mit Datentyp $L_{U}=Nil|[U,L_{U}]$ mit $U=L_{U}|E$ wobei weitere elementare LISP-Datentypen bezeichnet, der zentrale Datentyp der Programmiersprache LISP. Sogar LISP-Programme sind selbst solche Listen.

Doppelt verkettete Liste

Doppelt verkettete Liste mit drei Werten

Im Gegensatz zur einfach-verketteten Liste hat jedes Element sowohl einen Zeiger auf das nachfolgende als auch auf das vorhergehende Element.

Der Vorgänger-Zeiger des ersten und der Nachfolger-Zeiger des letzten Elementes zeigen auf den Wert NULL. Dieses besondere Element dient zum Feststellen des Anfangs und des Endes einer doppelt verketteten Liste.^[1]

Vorteile

Das Entfernen eines Elements aus der Liste kann in geschehen, auch wenn die Ankunft beim Element über keine der zwei Verkettungen geschah. (In diesem Fall müsste bei der einfach verketteten Liste der Vorgänger gesucht werden.)
Über die Liste kann von hinten nach vorne iteriert werden.

Nachteile

Höherer Speicherbedarf für die zusätzlichen Zeiger.
Beim Löschen und Einfügen müssen auch die Vorgänger-Zeiger der nachfolgenden Listenelemente angepasst werden.

Weitere Formen

Listenkopf

Der Listenkopf (oder Listenanker) ist ein Datenfeld, welches zusätzliche Informationen, wie beispielsweise die Anzahl der Knoten in der Liste, enthalten kann. Er zeigt auf das erste Element.

Skip-Liste

Wie verkettete Listen werden auch bei der Skipliste die Daten in Containern abgelegt. Diese enthalten einen Schlüssel und einen Zeiger auf den nächsten Container. Allerdings können Container in Skiplisten auch Zeiger auf andere Container enthalten, welche nicht direkt nachfolgen. Es können also Schlüssel übersprungen werden. Jeder Container hat eine bestimmte Höhe h, welche um 1 kleiner ist als die Anzahl der Zeiger, die ein Container enthält. Die Zeiger werden von 0 bis h nummeriert. Grundsätzlich imitiert eine Skipliste also die Binäre Suche auf einem Feld.

Skip-Liste mit mehreren Sprüngen

Bei den Skip-Listen unterscheidet man drei Arten von Typen:

ausgeglichene SkipList
unausgeglichene SkipList (siehe Bild)
randomisierte SkipList

Bei allen Typen ist das mehrfache Auftreten des Inhaltes erlaubt. Allerdings sind die aus- und die unausgeglichene SkipList geordnet, wohingegen die randomisierte SkipList nicht notwendigerweise geordnet sein muss. Durch das Einfügen von Zwischenstationen, welches den Aufwand der Implementierung erhöht, kann die mittlere Zugriffszeit (und damit verbunden die Komplexität) gesenkt werden. Eine Erweiterung des SkipList-Prinzip ist die Verknüpfung mit dem Prinzip der doppelt verknüpften Liste, wodurch „Rücksprünge“ ermöglicht werden. Bei einer ausgeglichenen SkipList senkt dies allerdings nicht die Komplexität, wohingegen bei einer unausgeglichenen SkipList auf Zwischenstationen verzichtet werden kann, welches dann wiederum den Zugriff auf Elemente in der Nähe der nächsten Zwischenstation erhöht.

Die Operationen Einfügen, Suchen und Löschen haben jeweils eine erwartete Laufzeit von $\mathcal{O}(\log n)$ .

Berechnung der Containerhöhe

Bei der randomisierten Skipliste erfolgt die Berechnung der Höhe h nach dem Zufallsprinzip. Die Wahrscheinlichkeit, dass eine bestimmte Höhe erreicht wird, kann folgendermaßen ermittelt werden: $\frac{1}{2\cdot 2^h}$

Bei nicht randomisierten Skiplisten wird die Höhe so bestimmt, dass jeder Zeiger mit Zeigerhöhe z auf einen Container 2^z Positionen weiter hinten in der Liste zeigen kann – also alle Container dazwischen eine geringere Höhe haben als der Zeiger.

Adaptive Listen

Da der Aufwand des Zugriffes auf ein Element einer einfach verknüpften Liste mit der Entfernung vom Start pro Einzelschritt zunimmt, kam man auf das Prinzip der adaptiven Listen. Im Versuch, diesen Aufwand (im Mittel) möglichst niedrig zu halten, werden die Listenelemente nach ihrer Zugriffshäufigkeit sortiert (vergangenheitssortiert). Dabei gibt es drei grundsätzliche Strategien:

MoveToFront: Bei jedem Zugriff auf ein Element wird dieses entfernt und am Anfang der Liste eingefügt.
Transpose: Bei jedem Zugriff auf ein Element wird es mit seinem Vorgänger vertauscht (Sonderfall: erstes Element)
Gratification: Zu jedem Element wird dessen Zugriffshäufigkeit gespeichert. In einem bestimmten Intervall wird anhand der Zugriffshäufigkeit die Liste neu sortiert.

Listen in der objektorientierten Programmierung

In der objektorientierten Programmierung zeichnen sich Listen gemäß dem Prinzip der Kapselung durch eine Menge von Listenoperationen aus. Intern können dabei unterschiedliche und durchaus auch kompliziertere Datenstrukturen, wie binäre Bäume zum Einsatz kommen. Aufgrund der internen Datenstruktur können dabei oft auch weitere Funktionen, wie beispielsweise Sortierung, sortiertes Einfügen, Entfernen des größten Elementes, etc. angeboten werden.

Je nach Einsatzzweck kann es sinnvoll sein, zwischen konkreten Implementierungen der Schnittstelle Liste zu wählen. Wird beispielsweise hauptsächlich wahlfrei über Index auf die Liste zugegriffen, wäre eine verkettete Liste eine schlechte Wahl, da dort n Operationen nötig sind, um das n-te Element zu adressieren.

Daher werden in objektorientierten Bibliotheken oft neben der Schnittstelle verschiedene konkrete Implementierungen angeboten. Beispielsweise gibt es in der Programmiersprache Java als Schnittstelle java.util.List, und es werden unter anderem java.util.LinkedList und java.util.ArrayList als konkrete Implementierungen angeboten. In C++ werden Listen und Vektoren in der Standardbibliothek implementiert.

Beispiele

Nachfolgend Beispiele in Pseudocode (an C angelehnt). Dabei gibt es in der Liste das Feld Key (also den Schlüssel, den man sucht) und das Feld Data (die Nutzdaten, die hinter dem Schlüssel stecken). Das Beispiel:

Gib mir die Lottozahlen vom 1. Januar 2006. Dabei ist 1. Januar 2006 der Schlüssel und die Lottozahlen sind die Nutzdaten.
pNext in einem Knoten (Element) ist der Zeiger auf das nächste Element in der Liste

Neues Element in Liste einfügen

   FUNKTION insertElement( Datum, Lottozahlen )
   {
      Zeiger *NeuesElement = Speicherallozierung(size(Datum) + size(Lottozahlen));

      WENN (Speicherallozierung erfolgreich)
      {
         Kopieren von Datum und Lottozahlen nach *NeuesElement;
         NeuesElement->pNext = NULL;
         Zeiger *LetztesElement = FindeLetztesElement();

         WENN (Letztes Element gefunden)
         {
            LetztesElement->pNext = NeuesElement;
            return GELUNGEN;
         }
         SONST
         {
            return FEHLER;
         }

      }
      SONST
      {
         return FEHLER;
      }
   }

Element suchen

   FUNKTION sucheElement( Datum )
   {

      Variable lz = NULL;
      Zeiger *AktuellesElement = ErstesElement();

      WENN (Erstes Element gefunden)
      {
         SOLANGE (lz == NULL UND AktuellesElement != NULL)
         {
            WENN (AktuellesElement->Datum == Datum)
               lz = AktuellesElement->Lottozahlen;
            SONST
               AktuellesElement = AktuellesElement->pNext;
         }

         WENN (lz != NULL)
            return lz;
         SONST
            return FEHLER;
      }
      SONST
      {
         return FEHLER;
      }
   }

Element aus Liste löschen

   FUNKTION deleteElement( Datum )
   {
      Zeiger *aktuellesElement = NULL;
      Zeiger *nächstesElement = ErstesElement();

      SOLANGE ( nächstesElement != NULL )
      {
         WENN (nächstesElement->Datum == Datum) // ''zu löschendes Element gefunden''
         {
            WENN ( aktuellesElement != NULL ) // ''wir befinden uns nicht am Listenbeginn''
            {
               WENN ( nächstesElement->pNext != NULL) // ''wir befinden uns nicht am Listenende''
               {
                  aktuellesElement->pNext = nächstesElement->pNext;
                  Lösche nächstesElement;
               }
               SONST // ''wir befinden uns am Listenende''
               {
                  aktuellesElement->pNext = NULL;
                  Lösche nächstesElement;
               }
            }
            SONST // ''wir befinden uns am Listenbeginn''
            {
               WENN ( nächstesElement->pNext != NULL) // ''wir befinden uns nicht am Listenende''
                  Setze Listenbeginn auf nächstesElement->pNext;
               SONST // ''wir befinden uns am Listenende - wir löschen das einzige Element, Liste ist nun leer''
                  Setze Listenbeginn auf NULL;

               Lösche nächstesElement;
            }
         }
         AktuellesElement = nächstesElement;
         nächstesElement = nächstesElement->pNext;
      }
   }

Verwendung von Liste in objektorientierter Sprache

Dieses Beispiel zeigt die Verwendungen einer Liste in C++.

#include <iostream>
#include <list>

using namespace std;

...

// Initialisierung
list<int> liste;

// am Anfang einfügen
liste.push_front(4);
liste.push_front(3);

// am Ende anfügen
liste.push_back(5);
liste.push_back(6);

// die Liste enthält 3 4 5 6
// Durchlaufen der Liste
for (auto it = liste.begin(); it != liste.end(); ++it)
{
   cout << *it << " ";
}

// Entfernen aller Zahlen größer als 4
liste.erase(remove_if(liste.begin(), liste.end(), [](int x) { return x > 4; }), liste.end());

// Sortieren
liste.sort();

// Löschen
liste.clear();

Anmerkungen

↑ ^a ^b Der Einsatz eines Wächterzeigers oder Sentinels anstelle des Null-Zeigers kann einen Vergleich in der Suchschleife sparen.

Basierend auf einem Artikel in:

Wikipedia.de