Bag / Multimenge (Algorithmus 1.4)

So geht’s: Oben eine Zahl mit add in den Bag legen oder eine Zufallszahl nehmen. add sieht genauso aus wie push beim Stapel. Herausnehmen kann man nichts, nur durchlaufen: „for (x : bag)“ zeigt den Iterator, wie aktuell von first über next wandert. „Mittelwert & Standardabweichung“ ist der typische Anwendungsfall: Ein kleiner Client läuft zweimal über alle Werte, einmal für die Summe, einmal für die Abweichungen, und man sieht die Zwischensumme Knoten für Knoten. Die „Beispielwerte“ sind zehn Messwerte, „↺ Neu starten“ setzt alles zurück.

Erklärung

Bag / Multimenge (Algorithmus 1.4). Die einfachste der vier Strukturen: Man kann Elemente hineinwerfen und alle durchlaufen, aber nichts gezielt herausnehmen. Die Reihenfolge spielt keine Rolle, Duplikate sind erlaubt.

Aufbau:

• Verkettete Liste wie beim Stapel [15], nur first.
• add(item) ist Wort für Wort push(): neuer Knoten vorne dran.
• Kein pop, kein dequeue. isEmpty() und size() wie beim Stapel, daher hier weggelassen.

Der Iterator, das eigentlich Neue auf der Seite:

• implements Iterable<Item> plus iterator() macht for (Item x : bag) möglich.
• ListIterator hält einen Zeiger current, der bei first startet.
• hasNext(): Gibt es noch einen Knoten (current != null)?
• next(): Wert holen, current auf current.next weiterschieben.
• remove(): leer, nicht unterstützt.

Wofür? Immer wenn man nur sammeln und später auswerten will, z. B. Messwerte einlesen und dann Mittelwert und Standardabweichung berechnen. Später im Buch (Kapitel 4) sind die Adjazenzlisten der Graphen genau solche Bags: Für jeden Knoten werden die Nachbarn gesammelt, die Reihenfolge ist egal.

Bezug zu den anderen: Genau dieser Iterator-Code ist das, was in [15] und [16] fehlte. Stapel und Schlange mit verketteter Liste bekommen ihn eins zu eins dazu. Im Fließtext steht übrigens „Algorithmen 1.1 und 1.2“, gemeint sind aber die Listenversionen 1.2 und 1.3. Algorithmus 1.1 hat seinen eigenen ReverseArrayIterator schon dabei.

Kapitel 1.3 komplett:

• Algorithmus 1.1: Stapel mit Resizing-Array (LIFO)
• Algorithmus 1.2: Stapel mit verketteter Liste (LIFO)
• Algorithmus 1.3: Warteschlange mit verketteter Liste (FIFO)
• Algorithmus 1.4: Bag mit verketteter Liste (Reihenfolge egal, nur hinzufügen und durchlaufen)