2.10. array, list, stack, queue, set und d_int_set im Vergleich

Lernziele

Wann benutzt man welchen einfachen Containertyp?
Eine Übersicht über die einfachen Containertypen von LEDA

Eine der häufigsten Fragen zu den einfachen Containertypen von LEDA lautet schlicht „Wann benutze ich denn welchen dieser Typen?“ oder „Ich muss mir Objekte eines Typs T merken und später wieder darauf zugreifen bzw. nachschauen, ob ich ein bestimmtes Objekt schon einmal gesehen habe. Nehme ich da jetzt eine list oder ein set oder was?“ Dieser Abschnitt versucht, das bisher über diese Typen Gesagte in Form von Tabelle 2.1 zusammenzufassen und Faustregeln zu deren Verwendung zu geben; n steht darin für die Anzahl der zu einem bestimmten Zeitpunkt in der Struktur gespeicherten Elemente.

Das wichtigste Entscheidungskriterium ist sicher der Typ der Elemente, die verwendet werden sollen. In einem d_int_set können nur ganzzahlige Werte gespeichert werden, die zudem aus einem nicht allzu großen Intervall stammen sollten. Bei einem set muss der Schlüsseltyp linear geordnet sein.

Eine lineare Ordnung lässt sich meist leicht selbst definieren, so dass man - falls die Struktur keine spezielle Funktionalität unterstützen muss - meist vor die Wahl zwischen array, list und set gestellt ist. Hier spielt dann die Zugriffszeit eine große Rolle. Als Faustregel kann man sagen: Wird hauptsächlich lesend zugegriffen, und ist die Stelle des Zugriffs bekannt, ist ein array vorzuziehen. Werden dagegen oft Elemente hinzugefügt oder gelöscht, so ist eine list oder ein set meist die bessere Wahl, ein set vor allem dann, wenn der Ort des Einfügens oder des Löschens nicht bekannt ist. Allerdings können in einem set keine Elemente doppelt vorkommen.

Ein weiteres, wichtiges Kriterium ist die Funktionalität des Containertyps. stack und queue kommen nur in Frage, wenn die Zugriffe auf die Elemente nur an einem bzw. an beiden Enden der Struktur vorgenommen werden und wenn nicht über alle Elemente der Struktur iteriert werden muss. Weiterhin spielt die Frage eine Rolle, ob die Struktur in mehrere Teilstrukturen aufgespalten, oder Teilstrukturen zu einem Ganzen vereinigt werden sollen; in diesem Falle scheiden stack und queue aus, und auch array unterstützt dies nicht direkt.

Tabelle 2.1. array, list, stack, queue, set und d_int_set im Vergleich

  array list stack, queue set d_int_set
Elementtyp beliebig beliebig beliebig linear geordnet ganzzahlig, aus kleinem Intervall
Zugriffszeit O(1) bei bekanntem Index, O(n) im schlechtesten Fall O(1) bei bekanntem Item, O(n) im schlechtesten Fall O(1), nur auf Endelement(e) O(log(n)) O(1)
Zeit für Einfügen und Löschen eines Elementes O(n) im schlechtesten Fall O(1) O(1), nur am Ende O(log(n)) O(1)
Aufspalten, aneinanderhängen, mischen möglich? nur durch zusätzliches array ja nein Aufspalten durch diff(), mischen durch join() Aufspalten durch diff(), mischen durch join()
Doppelte Elemente möglich? ja ja ja nein nein
Iteration über Elemente ja, durch for-Schleife ja, durch forall-Makros nein ja, durch forall-Makro nur durch Iteration über das gesamte Intervall
Platzverbrauch gering mittelmäßig gering bis mittelmäßig mittelmäßig sehr gering

Die Klasse slist ist noch platzeffizienter als die Klasse list, besitzt aber eine wesentlich kleinere Funktionalität.

Ebenso sind b_stack und b_queue platzeffizienter als stack bzw. queue, müssen aber die Anzahl der zu speichernden Elemente im Voraus kennen.

Die Einfügezeit von int_set ist amortisiert gesehen ein wenig geringer als die von d_int_set; dafür muss das Intervall, aus dem die ganzzahligen Elemente stammen, im Voraus bekannt sein, und die Funktionalität ist ggü. d_int_set eingeschränkt.

[Tip] Tipp

LEDA besitzt keine spezielle Klasse zur Realisierung einer Bag, d. h., eines einfachen Containertyps, in dem Elemente doppelt vorkommen dürfen, und bei der der Zugriff auf ein Element, das Einfügen und das Löschen eines Elementes in kurzer Zeit, d. h. O(log(n)) im schlechtesten Fall, möglich ist.

In dieser Situation können die assoziativen Containertypen hilfreich sein, die wir in Kapitel 3, Assoziative Containertypen kennen lernen werden. Eine Möglichkeit, Duplikate in einer solchen Struktur zu speichern, ist die folgende: Die zu speichernden Elemente werden als Schlüssel der Schlüssel-Wert-Paare verwendet, und der assoziierte Wert zählt mit, wie oft ein bestimmtes Element gespeichert ist.