50. Listen: Implementation IV

int list_deleteAt(List *l, int index)
{
  Node *toDel;

  if (index==0) {
    toDel = l->first;
    l->first = toDel->next;
    if (!l->first) {
      l->last = NULL;
    }
  } else {
    Node *prev=getNodeAt(l, index-1);
    if (!prev) {
      return -1;
    }
    if (!(toDel = prev->next)) {
      return -1;
    }
    prev->next = toDel->next;
    if (!prev->next) {
      l->last = prev;
    }
  }
  freeNode(toDel);
  return 0;
}

Golden Rule: If you have too many special cases, you are doing it wrong.

Außerdem enthält dieser Code einen Fehler, den wir später mit einem Debugger finden werden.

In diesem Fall könnte man an Sentinel Values für den Anfang und das Ende denken, um die Spezialbehandlungen überflüssig zu machen. Das komplizierte Handling mit dem Vorgängerknoten prev ließe sich durch doppelte Verkettung umgehen – dafür aber würden wir mit ansonsten erhöhter Komplexität bezahlen.

int list_insertBefore(List *l, char *item,
  int index)
{
  Node *new = getNodeFromContent(item);

  if (index>0) { /* Somewhere within the list */
    Node *cur=getNodeAt(l, index-1);
    if (cur) {
      new->next = cur->next; cur->next = new;
    } else { freeNode(new); return -1; }
  }
  else if (index==0) { /* Insert at start */
    if (!l->first) l->last = new;
    new->next = l->first; l->first = new;
  } else { freeNode(new); return -1; }
  return 0;
}

Laufzeitbewertung

Laufzeiten werden in der Informatik üblicherweise in O-Notation in Abhängigkeit von der Menge der Daten gegeben. O(n) bedeutet, dass eine Funktion für große n doppelt so lange läuft, wenn sie doppelt so viele Daten zu bearbeiten hat, bei O(n²) ist das Verhältnis 4 : 1, bei O(exp(n)) ist es grob 8 : 1. Optimal sind O(1)-Funktionen: Ihre Laufzeit ist unabhängig von der Datenmenge.

Hintergrund der Notation ist der Grenzwertbegriff. Eine Funktion f(n) ist O(h(n)) – dabei soll h(n) eine einfachere Funktion sein –, wenn

das Verhältnis der beiden Funktionen also für eine wachsendes n konstant wird. Für uns ist der Wert der Funktion die Zahl der “Operationen”, die zur Berechnung der Funktion ausgeführt werden müssen (dabei vernachlässigt man üblicherweise, dass verschiedene Operationen verschieden lang dauern, weil das ohnehin stark von der verwendeten Maschine abhängt), während n die Datenmenge repräsentiert; bei der Liste wäre n die Zahl der Listenelemente.

Beispiel: f(n) = 7n² + 4n+ 1400. Für kleine n dominiert natürlich der konstante Anteil, schon für n= 6 hat aber der quadratische Term überholt und dominiert das Geschehen. f(n)∕n² geht gegen die Konstante 7, wir haben also O(n² ).

Funktionen, die O(nⁱ) sind, haben polynomiale Laufzeit, was für theoretische InformatikerInnen “gut” ist – schlimm sind dort exponentielle Laufzeiten der Art O(exp(n)). Probleme, für die nur Algorithmen mit exponentieller Laufzeit bekannt sind, heißen NP-hart.

In der Realität ist schon O(n³) ein guter Grund, nach besseren Methoden Ausschau zu halten, es sei denn, wir wissen, dass n klein ist. In der Tat bemühen sich viele NumerikerInnen, bessere Alternativen oder Näherungen für O(n² )-Algorithmen zu finden, beispielsweise bei N-Körpersimulationen. Für häufig verwendete Operationen, bei uns etwa das Anhängen an die Liste oder den Zugriff auf ein Element, will man sogar O(1) oder wenigstens O(log (n)).

Für reale Programme ist es nicht immer ganz einfach, die Komplexität abzuschätzen und vor allem, zu sehen, wo die ganze Rechenzeit hinläuft, selbst wenn man die Komplexität der einzelnen Algorithmen kennt. Der Computer kann dabei helfen, und zwar mit Programmen, die Profiler heißen. Wir kommen dazu, sobald wir wissen, was wir mit dieser Liste tun wollen.

This list sucks…

Die meisten Operationen, die diese Liste zur Verfügung stellt, sind O(n), weil die Liste immer durchsucht werden muss, um zu einem bestimmten Index zu kommen.

Zu wenig Fehlersicherheit.

Zu viel malloc (Verwaltungsoverhead) – Abhilfe könnte z.B. sein, in jedem Node z.B. 10k Daten oder 50 Strings zu speichern.

Wie gesagt: Bessere Listenimplementationen gibt es überall (z.B. in der glib – allerdings haben diese Listen ihre eigenen Tücken, vor allem, wenn man Python gewohnt ist).