verkettete Liste

[alzaimar]

Wie immer, muß man zwischen Theorie (Komplexitätsbetrachtung) und Realität unterscheiden.

Wie ich schon sagte, bei einem dynamischen Array muß man die Größe jeweils verdoppeln (oder jedenfalls um einen Faktor vergrößern), und nicht um einen konstanten Wert. Ein konstanter Wert wird die Komplexität von O(1) auf O(n) verschlechtern, eine Vergrößerung um einen Faktor ('2') eben nur marginal. Warum? Weil dieser Umstand bis im Zahlenraum von Integern nur maximal 31 mal vorkommen kann. Bei 2 Milliarden Werten ist der Aufwand dann zu verschmerzen und geht auch rein rechnerisch gegen 0.

Bei einer echten Anwendung, wie himitus MM (Memory-Manager?) wird gesucht, gelöscht, einfügt etc. Wer da die Nase vorn hat, hängt wirklich davon ab, was am häufigsten ausgeführt wird. Ich kann mir nicht vorstellen, das ein dynamisches Array, das anfangs auf ein paar 100k dimensioniert ist, performancetechnisch von einer LL abgehängt wird. Aber erst der Versuch macht schlau, und bis dahin vertraue ich himitsus Erfahrung.

Ich kann mir aber nun wirklich nicht vorstellen, das eine verkettete Liste in einer App gegenüber einer Skiplist oder Hashmap wirklich die Nase vorn hat. Na ja, vielleicht bei < 20 Elementen...