interne Funktionsweise eines Arrays

[Aphton]

Zitat von Gargamel:

Jetzt ergibt sich jedoch die Frage, was man macht, wenn die Anzahl der Elemente sehr stark variiert und es durchaus sein kann, daß viele Elemente in einem Rutsch hinzugefügt werden müssen.

Eine ausreichende Dimensionierung des Arrays ist in bestimmten Fällen nicht möglich, zumal wenn man auf einen mehr oder weniger effektiven Speicherverbrauch achten möchte.

Kommt ganz drauf an, was man mit dem Array (oder lieber Container) machen will.
Es ist ein Tradeoff zwischen Speicher & Geschinwidgkeit:
Entweder du kannst schnell über Index lesen/schreiben, dafür aber langsam einfügen/löschen - oder umgekehrt!

Array:
O(1) Lesen/Schreiben (Iteration)
O(n) Einfügen/Löschen

Verkettete Liste:
O(n) Lesen/Schreiben (Iteration)
O(1) Einfügen/Löschen

Wichtig ist noch, dass man bedenken muss, dass eine Liste für jedes Element einen Overhead von 4 (32bit) / 8 (64bit) Byte (Next Pointer - einfach verkettet) oder 8 (32bit) / 16 (64bit) (Next, Prev Pointer - doppelt verkettet) hat.

Wenn man nun eine Liste verwendet und beispielsweise darin 1.000 Integer Elemente hat, dann hat man insgesamt eine Größe von 1000 * SizeOf(Integer) * SizeOf(Prev/Next) = (32bit) 1000 * 4 * 8 = 32.000
Beim Array: 4 + 1000 * 4 = 4.004
(4 Bytes werden von Delphi insgeheim an der Adresse (ArrayPtr-4) angelegt, um die Länge zu merken)

Man kann übrigens noch schneller als O(n) sein, dafür ein Beispiel mit einem Binärbaum:
O(N * log N) Lesen/Schreiben
O(log N) Einfügen/Löschen

Du kannst ja mal erläutern, um was für Daten es sich handelt und in welcher Relation diese zueinander stehen.