Verschiedene Listen - Vor- und Nachteile

[queenmum]

Ich habe in genau einer Woche mündliches Abitur in Informatik. Hauptbestandteil der Prüfung wird auch Delphi sein. Wir hatten u.a. drei verschiedene Listen. Einmal eine Stapelliste, eine "normale" Liste und eine Baumstruktur. Kann mir jemand von euch die Vor- und Nachteile dieser drei Listen schildern?

Mehr Informationen zu den Listen:

TStapel: Die Stapelliste in eine, die - wie der Name schon sagt - wie ein Stapel funktioniert. Es kann nur das aus der Liste wieder genommen, werden, was zuvor als letztes hinzugefügt wurde. Beispiel: Ich gebe nacheinander die 4, dann die 5, und dann die 8 in die Liste. Ich kann als erstes erst wieder die 8 herausnehmen, dann die 5 und zuletzt die 4

TListe: Eine ganz normale Liste. Alles wird hintereinander angefügt, aber die einzelnen Objekte, die mittendrin liegen, auf diese ist nicht zugreifbar.

TBaum: Aufgebaut wie ein Baum. Unter einem Objekt liegen wieder zwei andere. Sieht ein wenig aus wie ein Stammbaum. Aber ich habe die Möglichkeit, mittendrin auf ein Objekt zuzugreifen.

So, kann mir jemand weiterhelfen?
Danke!

[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

[queenmum]

Dankeschön für deine Mühe! Das wirklich mal eine gute und präzise Antwort! Jetzt kann schon (fast) nichts mehr schief gehen!