Verschiedene Listen - Vor- und Nachteile

[Der_Unwissende]

Hi,
das eigentlich Wichtige ist, dass du die drei schon verstanden hast, mal ebend kann man da nicht alles erklären.
Die haben alle recht ähnliche Vor- und Nachteile.
Wichtigster Vorteil von ihnen ist es, dass du eine flexible Struktur hast. Sie wachsen dynamisch und verbrauchen dabei nur soviel Platz wie wirklich gerade benötigt wird.
Wichtigster Nachteil, du hast keinen wahlfreien Zugriff (auf das x-te Element).

Bei einem Stapel handelt es sich um eine LIFO (Last in first out) Struktur, bei einer normalen Liste (einer Queue) um eine FIFO Struktur (First in first out). Dabei ist es einfach nur wichtig diesen Unterschied zu beachten. Beide werden durchaus häufig verwendet und haben ihre Vorteile.
Wo und wie genau, dass musst du dann leider selbst wissen.

Bäume sind ein Spezialfall, es gibt zig Arten von Bäumen, die man sinnvoll einsetzen kann. In der Regel arbeitet man mit Binärbäumen, die zudem häufig Suchbaumeigenschaften besitzen. An sich trifft man auf AVL-, 2-3-, Rot-Schwarz- und viele weitere Bäume. Auch hier gilt, alle haben ihre Vor- und Nachteile (2-3 und Rot-Schwarz sind z.B. völlig gleichwertig).
Jedenfalls haben Bäume den Vorteil auch in der Breite zu wachsen. Wie du schon sagtest sind Bäume spezielle Listen oder genauer Listen entartete Bäume.
Besitzt ein Baum Suchbaumeigenschaften, so sortierst du neue Werte nach einem speziellen Muster ein. Am einfachsten guckst du ob der Wert im aktuellen Knoten kleiner oder größer dem neuen ist. Je nachdem machst du rekursiv links oder rechts weiter und suchst äquivalent. Damit sinkt die Zeit beim Suchen logarithmisch. Eine Liste müsstest du immer komplett betrachten.
Dies jedoch zu Ungunsten der Zeit des einsortierens. Das logarithmische gilt genau genommen nur, wenn dein Baum balanciert ist (links und rechts gleich hoch). Dies ist ein wichtiges Ziel und bedarf einigen Schritten. Je nach Baum kann es dabei zu unterschiedlichen Situationen kommen in denen die Knoten neu sortiert werden (auch das kostet Zeit).
Der größte Vorteil bleibt dabei, dass du schnell etwas suchen kannst, wenn du diese Eigenschaften ausnutzt. Einfügen und entfernen von Knoten führen dann aber leicht zum umsortieren um die Balance wieder herzustellen.

An sich gibt es jedoch keine Situation, in der ein Baum weniger geeignet sein dürfte als eine Liste (da es sich bei einer Liste nur um einen entarteten Baum handelt).

Gruß Der Unwissende