TList / dyn. Array - Was steckt dahinter?

[Mr_G]

Hallo zusammen,
mein Info-Lehrer hat mir gesteckt, dass sich hinter dynamsichen Arrays auch nur verkettete Listen verbergen und ich habe herausgefunden, dass die TList wiederum nur das OOP Pendant zu einem dynamischen Array ist.
Nun hätte ich mal rein interessehalber die Frage, wie das denn nun funktioniert.
Gruß Mr_G

[Nikolas]

Das ein dynamisches Array ein verkettete Liste ist, glaube ich nicht. Das interessante bei einem Array ist doch die konstante Zugriffszeit. Bei einer Liste hast du immer eine Zugriffzeit, die linear zur Größe der Liste ist.
Ich habe gelernt, dass ein dynamisches Array ein normales Array ist, dessen Größe automatisch verdoppelt wird, wenn es voll ist, bzw halbiert, wenn es nur noch zu 25% gefüllt ist. (Werte ohne Gewähr, sollte auch von der Implmenetierung abhängen.)
Damit hast du (amortisiert) alle Aktionen (lesen, schreiben, löschen) in konstanter Zeit.

[grenzgaenger]

'n dyn. array ist keine verkettet liste. denn die verkettete liste ist eine dynamische datenstruktur, das dyn.array nicht.

das dyn.array ist nix anderes als eine array of pointer, welche dynamisch vergrössert und verkleinert wird. das macht man entweder mit der hand oder man lässt es machen (z.b. tList, welches die entsprechenden routinen bereits integriert hat).

[SirThornberry]

Ein dynamisches Array ist in Delphi definitiv keine verkettete Liste. Es handelt sich bei Arrays in Delphi um zusammenhängenden Speicher. Schreibt man also über Elemte X drüber hinaus schreibt man in Element X+1 hinein. Da die Elemente direkt hintereinander liegen macht es auch keinen Sinn zusätzlich diese miteinander durch Pointer zu verketten da durch Berechnung klar ist wo ElementX liegt.

Zitat:

das dyn.array ist nix anderes als eine array of pointer

Auch das stimmt nicht wobei ich denke das du das richtige meinst. Ein dynamisches Array ist kein Array of Pointer sondern ein Pointer auf zusammenhängenden Speicher welcher durch den Compiler als Array angesprochen werden kann.

[Nikolas]

Wird bei einer Vergrößerung dann das alte Array in einen anderen Bereich kopiert oder besteht dass Array dann aus verschiedenen Stücken auf der Platte?

[Mr_G]

Danke für die zügigen Antworten!
Ich habe mir das irgendwie schon gedacht. Also entweder habe ich mich verhört oder mein Lehrer() hat unrecht...

Zitat von grenzgaenger:

...das dyn.array ist nix anderes als eine array of pointer...

Wieso of Pointer? Bei der Deklaration wird doch ein gewünschter einheitlicher Datentyp angegeben.

[grenzgaenger]

dein info lehrer hat unrecht.

ganz einfach, weil du in das array alles mögliche verpacken kannst. vorteil von der array struktur ist, dass du auf die jeweiligen elemente direkt zugreifen kannst, das ging mit einer liste oder baum nicht, somit hast du die möglichkeit effiziente sortieralgorithmen darauf zu implementieren.

'n pointer ist einfach die effizienteste datengrösse, welche dein prozessor abarbeiten kann (integer), und ist einfach eine adresse im speicher... nicht mehr, nicht weniger.

[DeddyH]

Zitat von grenzgaenger:

'n pointer ist einfach die effizienteste datengrösse, welche dein prozessor abarbeiten kann (integer), und ist einfach eine adresse im speicher... nicht mehr, nicht weniger.

Und eben deshalb so extrem flexibel, da die dahinterstehenden Daten von einem beliebigen Typ sein können.

[Zacherl]

Natürlich ist ein Array auch ein Pointer aber praktisch alle Datentypen in Delphi sind Zeiger, auch wenn man davon meist nichts direkt mitbekommt.
Die treffenste Beschreibung hier ist der zusammenhängende Speicherbereich. Da der Datentyp ja feststeht hat der Speicherbereich die Größe der Summe aller Elemente mal der Datentypgröße. (n * SizeOf(TDatenTyp))

[SirThornberry]

Zitat von Nikolas:

Wird bei einer Vergrößerung dann das alte Array in einen anderen Bereich kopiert oder besteht dass Array dann aus verschiedenen Stücken auf der Platte?

Das kommt auf den Speichermanager an. Wenn ich mich recht entsinne wird ReAllocMem verwendet. Einige Speichermanager schauen dann ob dahinter noch platz ist und somit entsprechend das array vergrößert werden kann. Andere hingegen reservieren einfach neuen speicherplatz und geben den alten frei.