Bei unsortierten Listen entsteht das Problem, daß beim Suchen eines Elementes in der Liste im schlimmsten Fall die gesamte Liste durchsucht werden muß. Würde man die Zugriffshäufigkeiten der Elemente im voraus kennen, könnte man die Elemente der Liste in der Reihenfolge ihrer Zugriffshäufigkeit anordnen, so daß die Elemente, auf die häufig zugegriffen wird möglichst weit vorn in der Liste stehen. Selbstanordnende Listen versuchen durch Umordnen der Liste bei jedem Zugriff die Zugriffszeit auf die Elemente der Listenelemente zu minimieren, ohne daß die Zugriffshäufigkeiten im voraus bekannt sein muß.
Inhalt des Vortrags:
Literatur:
T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen.
Spektrum Verlag (Kapitel 3.3)
Susanne Albers, Jeffery Westbrook. Self-Organizing Data Structures in: A. Fiat, G. Woeginger. Online Algorithms, The State of the Art. Springer Verlag, 1998.
Betreuer:
Thomas Kamphans