STP077: Liste von Listen

Als der inoffizielle Wikipedia-Vorlesepodcast sehen wir es als unsere Pflicht, eine Eigenheit dieser anzusprechen: nämlich Listen von Listen, obwohl es uns eigentlich um Listen im Speicher geht.Shownotes Rückbezüge: fundamentale Datenstrukturen siehe STP071: Felder/Listen, assoziative Datenfelder (Maps), Graphen Frage: Wie stellt man solche Datenstrukturen im Speicher dar? Gibt es darauf überhaupt die eine richtige Antwort? algorithmische Komplexität siehe STP029: Liste mit n Elementen ausdrucken in O(n), aber sortieren in O(n log(n)) bis O(n^2) Speicherallokation siehe STP047 und Speicherschutz siehe STP019: Bezug wird gleich klar werden Listen kann man als verkettete Liste darstellen klassisches Studienobjekt in Erstsemester-Datenstrukturen-Vorlesungen intuitiv verständlich: Parallele zu segmentierten Halsketten wahlweise einfach oder doppelt verkettet effiziente Operationen: Einfügen am Ende, Entfernen am Ende ineffiziente Operationen: Einfügen in der Mitte, Wahlzugriff/Suche Vergleichstabelle mit Darstellung der Zeiteffizienz alles in allem durchwachsene Performance -> geht es besser? alternative Strategie: interne Darstellung der Liste als balancierter Baum (oder evtl. "ausgeglichener Baum") außerdem Link auf die englische Wikipedia, die nicht nur unbalancierte, sondern auch balancierte Bäume zeigt kann nur sortierte Listen darstellen Idee: Wurzelknoten hat das Median-Element, dann der linke Ast alle kleineren und der rechte Ast alle größeren Elemente im Grunde alle gängigen Operationen mittelschnell: Wahlzugriff/Suche, Einfügen an beliebigen Stellen, Entfernen von beliebigen Stellen (Änderungen erfordern im Allgemeinen ein Austarieren des Baumes) große Variation von Implementationsstrategien für dieses Balancieren -> hier nicht verkettete Listen und balancierte Bäume sehen auf dem Papier ziemlich effizient aus, haben aber in ihrer reinen Form pathologisch schlechtes Speicherverhalten hoher Platzverbrauch: z.B. bei einfach bzw. doppelt verketteten Listen muss zu jedem Element müssen noch eine bzw. zwei Speicheradressen abgelegt werden hohe Allokationslast: wenn nicht eine Arena oder ein vergleichbarer Small Object Allocator verwendet wird schlechte Lokalität: beim Durchlaufen nachfolgender Eleme