05 – Listen

 

Einführung: statisches Feld (array)

Ein statisches Feld ist ein zusammenhängender Speicherbereich, der zur Speicherung mehrerer Werte des gleichen Typs verwendet wird, auf die mit Hilfe eines Index zugegriffen werden kann.

Anhand von Datentyp und Startadresse ist die Adresse des k-ten Elements ak direkt berechenbar.
Adressen können auch in Variablen gespeichert werden. Variable, die eine Adresse enthalten, heißen Zeiger (pointer). Variable, die als Hülle für einen durch einen Zeiger erschlossenen Speicherbereich dienen, heißen Referenz (reference):

Vorteil von Feldern: Extrem schneller Zugriff
Nachteil von Feldern: starre Größe (zur Vergrößerung müssen die Daten in einem neuen, größeren Feld gespeichert werden)

Dynamische Datenstrukturen

Dynamische Datenstrukturen wachsen automatisch mit steigendem Speicherplatzbedarf der in der Struktur enthaltenen Daten. Sie bauen auf einer Zeigerarchitektur auf und sind für bestimmte Operationen optimiert.

Lineare Liste

Das Ziel einer linearen Liste ist das Sammeln von Daten, die alle nacheinander verarbeitet werden sollen, auf die also sequentiell zugegriffen werden soll. Die Idee hinter einer Liste ist eine rekursive Datenstruktur:

Die “Link” Elemente der Liste kann man sich wie Karteikarten vorstellen. Auf jeder Karte steht eine Information und die Adresse der nächsten Karte (Die Adresse befindet sich in einer Zeigervariable, dies wird durch das Sternchen verdeutlicht). Man braucht also nur die Startadresse und kann sich von dieser durch die ganze Liste arbeiten. Diese Struktur hat den Vorteil, dass die Elemente irgendwo im Speicher sein können, statt einen zusammenhängenden Bereich zu bilden. Daher kann eine Liste ohne Probleme erweitert oder verkleinert werden.

Um die Operationen in der Liste zu beschleunigen und um sicherzustellen, dass auch eine leere Liste immer ein “erstes” und ein “letztes” Element hat, wird häufig vor die Liste noch ein zusätzliches Listenglied gesetzt, ein sogenanntes Dummy-Glied (sentinel node):

Beispiel für eine Liste
Um die Mitglieder eines Sportvereins zu speichern, speichert man eines der Mitglieder und gibt diesem einen Zettel mit der Adresse eines nächsten. Dieses nächste Mitglied hat wiederum eine Karte mit der Adresse eines anderen Mitgliedes. So kann man sich bei Bedarf durch die ganze Liste “durchfragen”, bis man zum gewünschten Element kommt.

Funktionen der einfach verketteten Liste (linked List):

  • traversieren: Aufsuchen aller Listeneinträge.
    • Realisierung:
      • Auf einer extra “Karteikarte” wird die Position des ersten Elementes gespeichert.
      • Die Leseposition wird auf 1 gesetzt.
      • Der Inhalt des Listengliedes, auf das die Position verweist, wird gelesen.
      • Die Adresse des nächsten Gliedes wird gelesen und in der “Karteikarte” gespeichert.
      • Dies geschieht, bis es keinen Nachfolger mehr gibt.
    • Rechenaufwand zum Traversieren:
      • Durchgehen aller Elemente: O(n)
      • Suchen eines Elementes mit vorgegebenen Daten:
        • schlechtester Fall: n Schritte
        • bester Fall: 1 Schritt
        • Durchschnitt: n/2 Schritte
        • Erfolglose Suche: n Schritte
  • push: Einfügen eines neuen Elementes am Anfang der Liste.
    • Realisierung:
      • Der Funktion push() werden die in dem neuen Listenelement zu speichernden Daten übergeben
      • Es wird ein neues Listenelement erstellt
      • Das erste Element der Liste wird lokalisiert, in der Variable “next” des neuen Elementes wird die Adresse des ehemaligen ersten Elementes gespeichert.
    • Rechenaufwand: immer O(1), unabhängig von der Länge der Liste
  • pop: Löscht das erste Element aus der Liste. Realisierung und Rechenaufwand analog zu pop

Es können in einer verketteten Liste keine Einträge an beliebigen Stellen eingefügt oder gelöscht werden. Dies lässt sich an dem Beispiel mit den Mitgliedern eines Vereins veranschaulichen:
Mitglied Nr. x soll gelöscht werden. Hierzu muss es aus der Liste entfernt werden. Der Zettel von Mitglied x, auf dem die Adresse von Mitglied x+1 steht, muss daher dem Mitglied x-1 übergeben werden, damit die Liste wieder verkettet ist. Mitglied x kennt zwar seinen Nachfolger, das Mitglied x+1, nicht aber seinen Vorgänger, das Mitglied x-1. Der Zettel kann also nicht übergeben werden.

Zu diesem Zweck gibt es doppelt verkettete Listen (doubly linked list):

Es wird in jedem Listenglied sowohl der Vorgänger als auch der Nachfolger gespeichert. Dieses Konzept nennt man Zweiwegverzweigerung.

Durch die Zweiwegverzweigerung mögliche Funktionen:

  • insert: Fügt ein Element an beliebiger Stelle ein.
  • delete: Löscht ein Element an beliebiger Stelle. Realisierung wie im Beispiel beschrieben, Vorgänger ist ja bekannt.

Spezielle Arten von Listen

Ringliste (circularly-linked list)
In einer Ringliste sind alle Elemente vorwärts und rückwärts verkettet. Das erste Element zeigt auf das letzte, das letzte auf das erste, so bildet sich ein Ring. Beim Traversieren einer Ringliste muss die Startposition gespeichert werden, damit sich keine Endlosschleife ergibt. Abgesehen davon ist die Ringstruktur ein Vorteil, da von jedem beliebigen Startelement aus traversiert werden kann.

intrusive Liste
Die Daten sind direkt in der Liste gespeichert. Dies entspricht der bisher verwendeten Struktur.
Diese Version wird normalerweise aber nicht verwendet, da sie nicht besonder flexibel ist.

nicht intrusive Liste
Die Daten sind über Zeiger an die Liste angehängt:

Die Variable Data hat nun keinen Wert mehr, sondern wurde zu einem Zeiger (deutlich durch das Sternchen) und zeigt auf die ausgelagerte Struktur vom Typ Data. Dies hat den Vorteil, dass Daten in mehreren Listen verwendet werden können:

Wenn die Daten aus einer Liste gelöscht werden sollen, muss hierbei beachtet werden, dass nicht die Daten selbst, sondern nur der Zeiger aus der Liste gelöscht wird, da die Daten auch noch in einer anderen Liste verwendet werden könnten.
Wenn Daten in keiner Liste mehr verwendet werden, sollten sie allerdings komplett gelöscht werden, da sie sonst zu einem memory-leak führen können.

Anwendungen von Listen

Listen werden häufig benutzt, um “Haufen”-Strukturen zu implementieren. Haufen (stacks) zeichnen sich dadurch aus, dass jeweils das Element, das zuletzt hinzugekommen ist, zuerst wieder die Liste verlässt.

Eine andere Anwendungsmöglichkeit ist die Warteschlange (queue). Hier wird das Element, das als erstes in die Liste gekommen ist, auch zuerst bearbeitet.

Nachteile von Listenstrukturen

Ein großer Nachteil von Listen ist, dass zum Beispiel der Zugriff auf das fünfte Element nicht direkt möglich ist. Statt dessen müssen erst alle Vorgänger bzw. Nachfolger aufgesucht werden. Zudem sind Operationen wie sortieren oder tauschen von Elementen extrem aufwändig.

Ähnliche Artikel

Kommentar verfassen