2.3.1. Grundlegende Operationen auf Listen

Lernziele

Die Klasse list
Einfügen und Löschen von Elementen am Anfang und am Ende einer Liste
Iterieren über die Elemente einer Liste mit forall und forall_rev
Die LEDA-Regeln 11 und 12

Das Unix™-Dienstprogramm tac liest alle Zeilen der Standardeingabe und gibt diese zeilenweise umgedreht wieder aus. Wie können wir dieses Programm mit Hilfe von LEDA implementieren? Wir müssen Zeile für Zeile lesen und jede Zeile in einer linearen Struktur speichern, um nach dem Lesen der letzten Zeile diese Struktur in umgekehrter Reihenfolge zu durchlaufen und somit alle Zeilen von der letzten bis zur ersten ausgeben zu können.

Welche Struktur wählen wir? Wir könnten uns für ein (eindimensionales) Array entscheiden. Darin können wir Strings (die die Zeilen enthalten) in einer linearen Abfolge speichern und sowohl von vorne nach hinten als auch umgekehrt darüber iterieren. Das ist aber keine gute Idee. Warum nicht? Weil wir nicht im Voraus wissen, wie viele Zeilen kommen werden! Zwar könnten wir jetzt sagen „Macht doch nichts, wozu gibt es das bequeme resize() in LEDA?“ Dann müssten wir aber entweder für jede neue Zeile ein resize() machen, was wegen des internen Umkopierens viel Speicherplatz und Zeit verschwenden würde. Oder wir könnten eine Verdoppelungsstrategie anwenden und dabei nur manchmal ein resize() machen, dann aber jedesmal die Größe des Arrays verdoppeln (oder um einen anderen konstanten Faktor vergrößern). (Siehe hierzu auch Übung 10.) Diese Strategie bedeutet aber zusätzlichen Verwaltungsaufwand für unseren Programmcode, was das Programm fehleranfällig macht. (Wir müssten uns merken, wie viele Elemente in dem Array wirklich gespeichert sind; diese Zahl würde i. Allg. kleiner als A.high() sein.)

Vergessen wir also die Idee mit dem resize(). Was wir dagegen brauchen, ist eine Datenstruktur, in die wir beliebig viele Elemente einfügen können, ohne vorher zu wissen, wie viele letztendlich kommen werden, und bei der im Moment des Einfügens die Anzahl der sich bereits in der Struktur befindenden Elemente keine Rolle spielt. Die Datenstruktur der Wahl ist hier eine lineare Liste, in LEDA implementiert durch die Klasse list.

Listen füllen und leeren

Hier ist das Programm. Es benutzt eine LEDA-Liste von Strings: list<string>. Es liest Zeile für Zeile in einen String ein und hängt diesen String an den Anfang der Liste an. Danach entfernt es nacheinander jeden String am Anfang der Liste und gibt diesen aus, bis die Liste wieder leer ist. Dadurch werden die Zeilen in umgekehrter Reihenfolge ausgegeben.

Filename: Tac.C
#include <LEDA/list.h>
#include <LEDA/string.h>
#include <iostream>

using leda::list;
using leda::string;

int main() 
{
  string s;

  list<string> L;

  while(std::cin) {
    s.read('\n'); // same as s.read_line() or s.read(cin,'\n')
    L.push(s);
  }
  
  while(!L.empty()) 
    std::cout << L.pop() << '\n';
}

Bei Eingabe der Zeilen

I was born in a cross-fire hurricane
And I howled at my ma in the driving rain,
But it's all right now, in fact, it's a gas!
But it's all right. I'm Jumpin' Jack Flash,
It's a gas! Gas! Gas!

gibt das Programm aus

 
It's a gas! Gas! Gas!
But it's all right. I'm Jumpin' Jack Flash,
But it's all right now, in fact, it's a gas!
And I howled at my ma in the driving rain,
I was born in a cross-fire hurricane

was lyrisch gesehen nicht weniger Sinn hat als die ursprüngliche Reihenfolge.

Listen sind wie Arrays ein Containertyp. Der Typparameter (hier string) muss bei der Definition angegeben werden.

Die Methode

L.push(x);

hängt ein Element mit Wert x an den Anfang einer Liste an.

L.pop();

entfernt das erste Elemente einer Liste und liefert es zurück. pop() hat dabei zur Vorbedingung, dass die Liste nicht leer ist.

L.empty();

prüft, ob eine Liste leer ist.

Zum Einlesen der Strings benutzen wir hier die Methode read() der Klasse string. Dieser kann als Argument ein Trennzeichen übergeben werden (das sich auch durchaus vom Zeilentrennzeichen unterscheiden kann). Sie liest dann alle folgenden Zeichen der Standardeingabe bis zu diesem Trennzeichen (ausschließlich) in den String.

[Note] Anmerkung

Es wird in obigem Programm am Anfang immer eine Leerzeile ausgegeben. Das liegt daran, dass am Ende noch ein Zeilentrennzeichen gelesen und als eigenständige (Leer-)Zeile angehängt wird. Das liegt an der Eingabestrom-Behandlung durch read(). Das letzte Zeilentrennzeichen sollte eigentlich konsumiert werden und der Strom dann leer sein. Dieses Fehlverhalten soll ab der Version 4.5 von LEDA behoben sein.

Anhängen und Entfernen von Elementen am Ende einer Liste

Lernen wir gleich noch einige weitere, einfache Operationen auf Listen kennen. Das folgende, algorithmisch ungeheuer anspruchsvolle Programm speichert 5 Zahlen in einer Liste, iteriert dann über die Liste und löscht die Zahlen wieder heraus. Das Anhängen und Löschen geschieht nun am Ende der Liste:

Filename: ListBasicOperations.C
#include <LEDA/list.h>
#include <iostream>

using leda::list;
using std::cout;
using std::endl;

int main() 
{

  list<int> L;

  L.append(5);
  L.append(3);
  L.append(1);
  L.append(5);
  L.append(2);

  cout << "There are " << L.size() << " elements in the list:\n";

  int x;

  forall(x,L)
    cout << x << " ";
  cout << endl;

  forall_rev(x,L)
    cout << x << " ";
  cout << endl;

  cout << "The first element is " << L.head() << endl; 
  cout << "The last element is "  << L.tail() << endl; 

  while(!L.empty()) 
    cout << L.pop_back() << " ";
  
  cout << endl;
}

Das Programm gibt Folgendes aus:

There are 5 elements in the list:
5 3 1 5 2
2 5 1 3 5  
The first element is 5
The last element is 2
2 5 1 3 5

Ein Aufruf von

L.append(x);

hängt ein Element mit Wert x am Ende einer Liste an. Abbildung 2.11 zeigt den Zustand der Liste nach allen append()-Operationen des obigen Programmes.

Abbildung 2.11. Einfügen und Löschen von Elementen am Anfang und Ende einer Liste

Einfügen und Löschen von Elementen am Anfang und Ende einer Liste

Ein Aufruf von

L.pop_back();

entfernt das Element am Ende einer Liste und liefert es zurück.

L.size();

liefert die Anzahl der Elemente, die sich gerade in der Liste befinden.

Die Methoden

L.head();
L.tail()

liefern das erste bzw. letzte Element der Liste L.

Abbildung 2.11 zeigt auch, dass die linearen Listen von LEDA intern doppelt verkettet sind, dass sie also genauso leicht von vorne nach hinten wie umgekehrt zu durchlaufen sind. Mehr noch: Sie sind sogar zirkulär, wie wir im nächsten Abschnitt sehen werden. Trotzdem gibt es immer einen definierten Anfang und ein definiertes Ende der Liste. head() bzw. tail() liefern die Elemente, die dort stehen.

Iterieren mit den forall-Makros

Das obige Makro

forall(x, L) { ... }

zeigt die typische Art und Weise, wie in LEDA über die Elemente einer Containerstruktur iteriert wird. Dadurch werden die Werte der Liste L nacheinander von vorne nach hinten der Variablen x zugewiesen. Das verwandte Makro

forall_rev(x, L) { ... }

durchläuft die Containerstruktur von hinten nach vorne. Diese Makros gibt es auch für viele andere Containertypen. Daneben gibt es noch einige andere forall-Makros, die wir alle nacheinander kennen lernen werden.

Beim Iterieren über Container sind einige Regeln zu beachten. LEDA-Regel 12 ist eine Regel, wie wir sie lieben: Normalerweise verbieten uns Regeln etwas, aber diese Regel sagt, dass wir innerhalb eines forall-Makros die Schleifensprung-Anweisungen break und continue wie gewohnt benutzen können. (Was wir oben nicht getan haben.)

[Warning] Warnung

Die Laufvariable x darf nicht innerhalb des Makros definiert werden, etwa durch

forall(int x, L) { ... }

Dann funktioniert die Makro-Expansion nicht mehr.

Diese Iterations-Makros sind in dem Sinne stabil, dass das Element, auf dem der Iterator x gerade steht, gelöscht werden darf. Das sagt LEDA-Regel 11 aus. Sie sagt allerdings auch Folgendes:

[Warning] Warnung

Eine Iteration mit den forall-Makros darf keine neuen Elemente zum Container hinzufügen.