Die Liste ist die letzte dynamische Datenstruktur der Reihe. Im Gegensatz zu Stack und Queue kann man in ihr an jeder Stelle einfügen, entfernen und lesen.

Die Liste stellt dafür ein aktuelles Element bereit, welches entweder zum Beginn, zum Ende oder zum nächsten Element verschieben kann.

Modellierung

Modellierung Node

Die Modellierung der Node ist schon aus Stack und Queue bekannt, diese verändert sich nicht.

Modellierung List

Die List speichert drei Pointer zwischen:

  • head zeigt auf das erste Element
  • tail zeigt auf das letzte Element
  • aktuell zeigt auf das aktuelle Element

aktuell ist ein Pointer auf ein Element der Liste, das man aktuell betrachtet. Es kann dabei von folgenden Methoden verschoben werden:

  • next() verschiebt zu seinem Nachfolger.
  • toFirst() verschiebt zum ersten Element.
  • toLast() verschiebt zum letzen Element.

Der Inhalt des aktuellen Element kann mit setContent() verändert werden.

Mit folgenden Methoden kann man neue Elemente anhängen:

  • append() hängt ein neues Element am Ende der Liste an.
  • insert() fügt ein neues Element vor dem aktuellen ein.
  • concat() verkettet zwei Listen.

remove() entfernt das aktuelle Element.

Algorithmen

Die Methoden der Klasse sind hier noch einmal aufgelistet, die interessanten auch erklärt.

isEmpty()

boolean isEmpty() {
  return head == null;
}

hasAccess()

boolean hasAccess() {
  return aktuell != null;
}

Eine Liste “hat Zugriff”, wenn aktuell auf ein Element zeigt. Dann kann man mit ihr arbeiten, “auf sie zugreifen”. Diese Methode ist hilfreich um durch die Liste zu iterieren, aber auch um in den anderen Methoden Fehlern vorzubeugen.

next()

void next() {
  if (!hasAccess()) return;
  aktuell = aktuell.getNext();
}

Verschiebt zum nächsten Element.

toFirst()

void toFirst() {
  aktuell = head;
}

Verschiebt zum ersten Element.

toLast()

void toLast() {
  aktuell = tail;
}

Verschiebt zum letzten Element.

getContent()

ContentType getContent() {
  if (!hasAccess()) return null;

  return aktuell.getContent();
}

Gibt den Inhalt des aktuellen Elements zurück.

setContent()

void setContent(ContentType content) {
  if (!hasAccess()) return;
  if (aktuell.getContent() == null) return;

  aktuell.setContent(content);
}

Setzt den Inhalt des aktuellen Elements.

append()

void append(ContentType content) {
  Node node = new Node(content);

  if (isEmpty()) {
    head = node;
    tail = node;
  } else {
    tail.setNext(node);
    tail = node;
  }
}

Hängt der Liste am Ende ein Element an. Die beiden Fälle sind schon aus der Queue bekannt.

insert()

void insert(ContentType content) {
  if (content == null) return;
  if (!hasAccess() && isEmpty()) return;
  if (!hasAccess() && !isEmpty()) {
    append(content);
    return;
  }
  Node node = new Node(content);

  if (aktuell == head) {
    node.setNext(head);
    head = node;
  } else {
    Node last = getNodeBefore(aktuell);
    last.setNext(node);
    node.setNext(aktuell);
  }
}

Fügt ein Element zwischen dem aktuellen und seinem Vorgänger ein.

Zu beginn werden die Sonderfälle abgearbeitet:

  • Falls Content unzulässig ist, passiert nichts. (Z. 2)
  • Falls wir keinen Zugriff haben und die Liste leer ist, passiert nichts (Z. 3)
  • Falls wir keinen Zugriff haben und die Liste nicht leer ist, wird stattdessen angehängt. (Z. 4)
  • Falls aktuell auf den ersten Wert zeigt, passiert das selbe wie beim Stack.

Sonst wird der Wert vor dem aktuellen mithilfe der unten erklärten Helfer-Funktion getNodeBefore() abgerufen und das neue Element zwischen dieses und das aktuelle eingeschoben.

getNodeBefore()
Node getNodeBefore(Node n) {
  Node node = head;
  while (
    node != null &&
    node.getNext() != n
  ) {
    node = node.getNext();
  }
  return node;
}

Diese Methode gibt das Element vor einem übergebenen Element n zurück. Es beginnt beim ersten Element und traversiert die Liste. Findet es das Element node, das vor n liegt, für das also nicht gilt node.getNext() != n (Z. 5), bricht es ab und gibt dieses Element zurück.

concat()

concat(List<ContentType> list) {
  if (list == null) return;
  if (list.isEmpty()) return;

  this.tail.setNext(list.head);
  this.tail = list.tail;
  list.head = null;
}

Diese Methode verkettet zwei Listen. Zuerst wird einigen Fehlern vorgebeugt: Wird null oder eine leere Liste übergeben, passiert nichts (Z. 2, 3).

Ist die übergebene Liste zulässig, werden die beiden Listen “angedockt”: An den eigenen tail wird der head der übergebenen Liste angehängt (Z. 5), dann wird der tail der übergebenen Liste zum neuen tail (Z. 6). Zum Schluss wird die übergebene Liste geleert: Dafür genügt es, den head dieser Liste auf null zu setzen (Z. 7).

Snippets

list.toFirst();
while (list.hasAccess()) {
  // Do something

  list.next();
}

Mit diesem Snippet kann man durch eine Liste iterieren.

Sortieren

Auf Listen lässt sich sehr idiomatisch sortieren. Besonders die rekursiven Verfahren Mergesort und Quicksort sind nahe an den Algorithmen.

Quicksort

List<Integer> quicksort(List<Integer> list) {
  // Rekursionsbasis
  if (list.isEmpty()) return list;

  List<Integer> a = new List<>();
  List<Integer> b = new List<>();

  list.toFirst();

  // Pivot auswählen
  int pivot = list.getContent();
  list.next();

  // Auf A und B aufteilen
  while (list.hasAccess()) {
    int current = list.getContent();

    if (current < pivot) { a.append(current); }
    else { b.append(current); }

    list.remove();
  }

  // A und B sortieren
  a = quicksort(a);
  b = quicksort(b);

  // Wieder zusammenfügen
  a.concat(list);
  a.concat(b);
  return a;
}

Mergesort

List<Integer> mergesort(List<Integer> list) {
  // Rekursionsbasis: Prüfen, ob Liste länger als 1 ist
  list.toFirst();
  list.next();
  if (!list.hasAccess()) return list;

  List<Integer> a = new List<>();
  List<Integer> b = new List<>();

  list.toFirst();

  // Auf A und B aufteilen
  for (int i = 0; list.hasAccess(); i++) {
    if (i % 2 == 0) { a.append(list.getContent()); }
    else { b.append(list.getContent()); }
    
    list.next();
  }

  // Rekursionsschritt
  a = mergesort(a);
  b = mergesort(b);

  // Zusammegefügt zurückgeben
  return merge(a, b);
}

List<Integer> merge(List<Integer> a, List<Integer> b) {
  List<Integer> result = new List<>();

  a.toFirst();
  b.toFirst();

  while (a.hasAccess() && b.hasAccess()) {
    if (a.getContent() < b.getContent()) {
      result.append(a.getContent());
      a.next();
    } else {
      result.append(b.getContent());
      b.next();
    }
  }

  while (a.hasAccess()) {
    result.append(a.getContent());
    a.next();
  }

  while (b.hasAccess()) {
    result.append(b.getContent());
    b.next();
  }

  return result;
}

SortedList

Oft braucht man einen sortierte Wertebereich.
Da Sortieren sehr aufwändig ist, kann man bei Listen einen anderen Ansatz verwenden:

Alle Elemente werden schon beim einfügen an die richtige Stelle sortiert. Dadurch ist die Liste zu jedem Zeitpunkt vollständig sortiert.

Dafür muss man im wesentlichen nur die insert()-Methode ändern.

void insert(ContentType content) {
  if (content == null) { return; }

  // If empty, use normal append()
  if (this.isEmpty()) {
    super.append(content);
    return;
  }

  // Go to first element
  this.toFirst();

  // Search correct position
  while (
    this.hasAccess() &&
    this.getContent().compareTo(pContent) < 0
  ) { this.next(); }

  // If this is not at the end, insert() - Else append().
  if (hasAccess()) { super.insert(content); }
  else { super.append(pContent); }
}

Diese Methode erweitert die ursprüngliche Liste, die mit super aufgerufenen Methoden sind also weiter oben aufgeführt.

Falls die Liste aktuell leer ist, kann man einfach hinten anfügen (Z. 4-7). Sonst wird das Element gesucht, welches bei einem Vergleich mit dem einzufügenden nicht kleiner ist (Z. 10-16).

Falls die Liste dann noch Zugriff hat (Z. 19) wird das Element davor eingefügt. Hat die Liste dann keinen Zugriff mehr, so ist der Algorithmus einmal durch die Liste iteriert und man kann hinten anhängen (Z. 20).

Nutzungsszenarien

In der Liste kann man dynamisch Daten speichern. Im Gegensatz zu Stack oder Queue kann man mit ihr jedoch alle Elemente betrachten, ohne die Liste verändern zu müssen. Aufwendiges Zwischenspeichern beim iterieren (wie es bei Stack oder Queue nötig wäre) benötigt man hier nicht.

Listen sind hilfreich um Datenmengen zu verarbeiten, deren Größe unbekannt ist, bei denen ich aber trotzdem auf alle Elemente zugreifen möchte. Damit sind sie ein Ersatz für Arrays, solange ich die Größe des Arrays nicht kenne.

In der Laufzeit hat dies den Vorteil, dass ich weder ein unnötig langes Array und somit viel Speicher alloziere, noch ein zu kurzes Array dass das Programm behindert erstelle. Ich muss außerdem nicht die Anzahl der belegten Werte im Array zwischenhalten, da in der Liste immer alle Werte belegt sind.