Zitat von
marabu:
Die fortgeschrittene Prozessortechnik hat uns flache Adressräume gebracht. Die zeiger-basierte Implementierung von Listen war keine Tugend sondern eher aus der Not geboren. Der Pferdefuß bei einer array-basierten Implementierung von Listen ist die dynamische Rekonfiguration, der wahlfreie Zugriff auf die einzelnen Listeneinträge macht das aber mehr als wett. Die Motivation für eine zeiger-basierte Implementierung kann heute nur noch aus extrem knappem Hauptspeicher bei rein sequentiellem Zugriff kommen.
"Echte" Listen haben gegenüber dynamischen Arrays den Vorteil, daß Einfüge-Operationen in konstanter Zeit geschehen, d.h. man nur next bzw. prev Pointer anpassen muß.
Bei dynamischen Arrays muß hingegen ein durchgehender Speicherblock "gefunden" und dann alles kopiert werden, was je nach Listengröße auch gar nicht machbar ist. Das wird zwar durch intelligente Memory-Manager und Alloziierung von größeren Blöcken gemindert, hat aber immer noch eine viel größere Laufzeit.
Was besser ist, dynamische Arrays oder "echte" Listen, hängt ganz vom Einsatzzweck ab und davon ob man viele Einfügeoperationen (besser Listen) oder viele Zugriffe hat (besser dynamische Arrays).
Implementierungen von echten Listen, Bäumen usw. gibt es bei
http://www.yunqa.de/delphi/
Ich dachte die JCL hätte sowas auch, habe aber dort nichts gefunden.