Liste (Datenstruktur)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Doppelt verkettete Liste)
Wechseln zu: Navigation, Suche

Die verkettete Liste ist eine dynamische Datenstruktur, die eine Speicherung von miteinander in Beziehung stehenden Objekten erlaubt. Die Anzahl der Objekte ist im Vorhinein nicht bestimmt. Die Liste wird durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.

Im Gegensatz zu Bäumen sind Listen linear, das heißt ein Element hat genau einen Nachfolger. Eine Liste kann zu einem Zyklus (zyklische Liste) geschlossen werden, indem der Zeiger des letzten Listenelementes so geändert wird, dass er auf ein beliebiges Listenelement zeigt. Dieses Listenelement (und nur dieses) hat dann zwei Vorgänger, alle anderen Elemente haben genau einen Vorgänger. Ob eine Liste zyklisch ist oder nicht, kann mit dem Hase-Igel-Algorithmus effizient festgestellt werden.

Vergleich mit anderen Datenstrukturen[Bearbeiten]

Arrays[Bearbeiten]

Im Gegensatz zu Arrays müssen die einzelnen Speicherzellen nicht nacheinander im Speicher abgelegt sein, es kann also nicht mit einfacher Adressarithmetik gearbeitet werden, sondern die Speicherorte müssen absolut referenziert werden. Der Vorteil einer Liste gegenüber einem Array ist, dass das Einfügen und Löschen von Elementen an jedem Punkt in der Liste in konstanter Zeit möglich ist. Dies liegt daran, dass nur Verweise neu gesetzt werden und nicht - wie bei Arrays - alle nachfolgenden Elemente verschoben werden müssen. Die Liste verbraucht jedoch mehr Speicher, da die Verweise auf andere Listenelemente gespeichert werden müssen.

Geschwindigkeit von Listen in der Praxis[Bearbeiten]

Dieser Vorteil von Listen gegenüber Arrays ist theoretisch zwar korrekt, jedoch in der Praxis oft nicht gegeben. Sobald Einfüge- und Löschoperationen an zufälligen Positionen stattfinden sollen, wo Listen ihren Vorteil der konstanten Zeit ausspielen könnten, muss in der Datenstruktur die richtige Position gefunden werden. Theoretisch sind in Listen und Arrays Suchoperationen gleich schnell, das heißt die Zeit steigt linear mit der Größe der Datenstruktur. In der Praxis läuft das Einfügen und Löschen jedoch bei großen Arrays wesentlich schneller ab, da die Datenstruktur immer in nicht fragmentierter Form im Speicher abgelegt wird. Listen hingegen werden in der Theorie als ideal geordnet modelliert, während sich die Listeneinträge in der Realität über den ganzen Speicherbereich verteilen. Durch diese Fragmentierung steigt die Zahl der Cache Misses stark an.

Knoten[Bearbeiten]

Ein Knoten (engl. node) bezeichnet ein Element der Liste, welches die Daten und einen Zeiger auf seinen Nachfolger enthält. Skizze

Typen[Bearbeiten]

Man unterscheidet grundsätzlich zwischen einfach und mehrfach oder doppelt verketteten Listen.

Einfach verkettete Liste[Bearbeiten]

Sie ist die einfachste Form der verketteten Liste, da sie neben den einzelnen Knoten nur einen „Start“-Zeiger besitzt. Dieser zeigt auf den ersten Knoten in der Liste. Der letzte Knoten in der Liste zeigt auf den Wert NULL (hier NIL für „Not In List”).

Verbale Definition: Eine Liste ist entweder leer oder sie besteht aus einem Kopf und einem Zeiger, der wiederum eine Liste ist.

Einfach verkettete Liste mit drei Werten
Einfach verkettete Liste mit fünfzehn Werten

Vorteile

  • Elemente können sehr schnell am Anfang der Liste eingefügt werden; sehr geringer Speicherbedarf
  • Im Gegensatz zu einem Array ist das Einfügen problemlos möglich, ohne dass der komplette Datensatz bei jeder Vergrößerung umkopiert werden muss

Nachteile

  • Es ist aufwändig nach Daten zu suchen, Knoten einzufügen, zu löschen und die Liste zu sortieren, da über jedes einzelne Element gegangen (iteriert) werden und das Einfügen an der ersten und der letzten Stelle gesondert behandelt werden muss.

Erweiterung[Bearbeiten]

Da sich die zuvor erwähnte Variante als zu umständlich (siehe Nachteile) erwiesen hat, wird als Erweiterung ein Zeiger auf das letzte Element eingeführt. Da man zum Anfügen an das Ende der Liste das letzte Element braucht, damit es auf die neuen Elemente zeigt, kann man dadurch schnell Elemente anfügen. In der normalen, einfach verketteten Liste müsste man sonst das erste Element nehmen und bis zum letzten durchgehen. Nachteilig wirkt sich ein etwas größerer Speicherbedarf aus, da man auch einen Zeiger auf das letzte Element speichern muss.

Doppelt (mehrfach) verkettete Liste[Bearbeiten]

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 Auffinden des Anfangs und des Endes einer doppelt verketteten Liste.

Vorteile

  • Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.
  • Schnelles Löschen und Einfügen von Elementen.
    • Das macht zum Beispiel das effiziente Sortieren der Liste möglich.
  • Über die Liste kann von hinten nach vorne iteriert werden.

Nachteile

  • Höherer Speicherbedarf für die zusätzlichen Zeiger.

Weitere Formen[Bearbeiten]

Liste mit Listenkopf[Bearbeiten]

Der Listenkopf oder Sentinel ist ein spezieller Knoten am Anfang der Liste, der zusätzliche Informationen, wie beispielsweise die Anzahl der Knoten in der Liste, enthält. Der wesentliche Vorteil ist, dass das Einfügen des 1. Elements kein Sonderfall ist.

Skip-Liste[Bearbeiten]

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:

  1. ausgeglichene SkipList
  2. unausgeglichene SkipList (siehe Bild)
  3. 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, welche die Möglichkeit eines „Rücksprunges“ ermöglicht. 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 2z Positionen weiter hinten in der Liste zeigen kann – also alle Container dazwischen eine geringere Höhe haben als der Zeiger.

Adaptive Listen[Bearbeiten]

Da der Aufwand des Zugriffes auf ein Element einer einfach verknüpften Liste mit der Entfernung vom Start um n Schritte zunimmt, kam man auf das Prinzip der adaptiven Listen. Dieses Prinzip geht von der Voraussetzung des zunehmenden Zugriffsaufwandes aus und sortiert die Listenelemente nach ihrer Zugriffshäufigkeit (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: 1. Element)
  • Gratification: Zu jedem Element werden dessen Zugriffshäufigkeit gespeichert. In einem bestimmten Intervall wird anhand der Zugriffshäufigkeit die Liste neu sortiert.

Listen in der objektorientierten Programmierung[Bearbeiten]

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,[1] und es werden unter anderem java.util.LinkedList[2] und java.util.ArrayList[3] als konkrete Implementierungen angeboten. In C++ werden Listen und Vektoren in der Standardbibliothek implementiert.

Listen in der Programmiersprache LISP[Bearbeiten]

Listen sind neben den Einzelwerten (Atomen) die Basisdatenstruktur der Programmiersprache LISP. Auch Programme sind dort Listen von Listen.

Beispiele[Bearbeiten]

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[Bearbeiten]

   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[Bearbeiten]

   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[Bearbeiten]

   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[Bearbeiten]

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();

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. java.util.List Java API Specification
  2. java.util.LinkedList Java API Specification
  3. java.util.ArrayList Java API Specification