Direkt zum Inhalt

Lexikon der Mathematik: selbstanordnende Liste

verkettete Liste, die sich nach jedem Zugriff selbst neu organisiert.

Beim Zugriff auf verkettete Listen kann es je nach Anwendung vorkommen, daß ein einmal gefundener Schlüssel im Lauf der nächsten Zeit noch mehrfach benötigt wird, und man deshalb die Liste noch häufiger nach ihm durchsuchen wird. Es ist daher sinnvoll, das im letzten Zugriff gefundene Element an den Kopf der Liste zu stellen und somit die Liste bei jedem Zugriff umzustellen, um beim nächsten Zugriff auf diesen Schlüssel die Zugriffszeiten zu reduzieren. Das Durchsuchen einer Liste nach diesem Verfahren heißt Durchsuchen einer selbstorganisierenden Liste oder auch Durchsuchen einer selbstanordnenden Liste.

Ein typisches Beispiel für eine selbstanordnende Liste ist die Tabelle der Symbole in Compilern für Programmiersprachen.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.