TList = verkettete Liste ? [erledigt]

[Hansa]

Zitat:

Zitat von marabu

...Die zeiger-basierte Implementierung von Listen war keine Tugend sondern eher aus der Not geboren...

Dann mache ich eben aus der Not eine Tugend. :mrgreen: Und die Not kam übrigens vom 64 KB Datensegment, was viel zu klein war. Deshalb wurde der Heap benutzt. Wie hat Bill Gates gesagt ? "Ich kann mir nicht vorstellen, daß es einmal eine Anwendung gibt, die mehr als 640 KB Speicher braucht". :lol:

P.S.: alles Richtung Array scheidet aus.

[Union]

Zitat:

Zitat von Hansa

Zitat:

Zitat von marabu

...Die zeiger-basierte Implementierung von Listen war keine Tugend sondern eher aus der Not geboren...

Dann mache ich eben aus der Not eine Tugend. :mrgreen: Und die Not kam übrigens vom 64 KB Datensegment, was viel zu klein war. Deshalb wurde der Heap benutzt. Wie hat Bill Gates gesagt ? "Ich kann mir nicht vorstellen, daß es einmal eine Anwendung gibt, die mehr als 640 KB Speicher braucht". :lol:

P.S.: alles Richtung Array scheidet aus.

Warum ? Was ist denn der konkrete Anwendungszweck?

[mael]

Zitat:

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.

[marabu]

Wie bitte?

Zitat:

Zitat von mael

"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ß.

Das mag ja für die Nachfahren Stack oder Queue gelten, aber für "echte" Listen gibt Dr. Landau immer O(n) an.

Zitat:

Zitat von mael

Bei dynamischen Arrays muß hingegen ein durchgehender Speicherblock "gefunden" und dann alles kopiert werden, was je nach Listengröße auch gar nicht machbar ist.

Da beschreibst du jetzt aber wirklich den Sonderfall.

Wenn das framework team von Delphi keine zeiger-basierten Stacks und Queues implementiert hat, dann deshalb, weil die wissen, dass die beiden Implementierungen (zeiger vs array) funktional gleichwertig sind - die trade-offs sind ja schon beschrieben worden. Wer kann, der trifft im Einzelfall eine qualifizierte Entscheidung, alle anderen benutzen die mitgelieferten Komponenten und fahren im Regelfall nicht schlecht damit.

Freundliche Grüße vom marabu

[Hansa]

Erledigt deshalb : erstens nützt es nichts lange rumzulamentieren wegen ca. 20-50 Zeilen. Die Listen (habe doppelt verkettete verwendet) sind total flexibel, komme was wolle. 8)

Allerdins eines noch :

Zitat:

Zitat von Hansa

Desweiteren kommt es mir so vor, daß next usw. in TList gar nicht existiert.

Zitat:

Zitat von Robert_G

:wall:

Die Antwort ist echt gut. :lol: Seltsamerweise ist bei mir zumindest in der Hilfe nichts von next und prev zu sehen. Gibts das jetzt oder etwa wirklich nicht ?

[Chewie]

Natürlich gibts das nicht, warum auch? In einem Array macht sowas keinen Sinn.

[Hansa]

Dann soll Robert_G mal bessere Antworten geben. Bei : :wall: denkt man, etwas übersehen zu haben ! Direktzugriff auf das Ding brauche ich keinen, sondern nur die Nachbarknoten. Also ist TList sowieso unbrauchbar.

[Dax]

Ach Hansa... :roll:

[mael]

Zitat:

Zitat von marabu

Wie bitte?
Das mag ja für die Nachfahren Stack oder Queue gelten, aber für "echte" Listen gibt Dr. Landau immer O(n) an.

Mit echten Listen meine ich die (doppelt) verketteten Elemente. D.h. Einfügeoperation braucht

Delphi-Quellcode:

NewElement := New(Element);
Insert(AtElement, NewElement)
begin 
  AtElement.Next.Prev := NewElement; 
  AtElement.Next := NewElement;
end;

Das heißt, ich gebe keinen Index an, sondern das Element nachdem ich einfügen will. Daher habe ich O(1).
Wenn man mit Indexen arbeitet (wahlfreier Zugriff) sind Listen nicht geeignet, aber häufig geht man von Anfang zum Ende einer Liste per next-Pointer. Der Algorithmus darf natürlich nicht, wie in Delphi üblich, mit Indexen funktionieren, sondern mit Pointern, sonst ergibt sich O(i) weil man i Elementen folgen muß um an die i-te Stelle zu gelangen und dort die Pointer auf das neue Element zeigen zu lassen.

Zitat:

Zitat von marabu

Zitat:

Zitat von mael

Bei dynamischen Arrays muß hingegen ein durchgehender Speicherblock "gefunden" und dann alles kopiert werden, was je nach Listengröße auch gar nicht machbar ist.

Da beschreibst du jetzt aber wirklich den Sonderfall.

Keineswegs, Einfügeoperationen sind teuer, da ich nicht einfach einen Pointer verbiege, sondern das Array redimensionieren und daher manchmal verschieben muß, da an der aktuellen Adresse nicht immmer genug Platz ist.

Zitat:

Zitat von marabu

Wenn das framework team von Delphi keine zeiger-basierten Stacks und Queues implementiert hat, dann deshalb, weil die wissen, dass die beiden Implementierungen (zeiger vs array) funktional gleichwertig sind - die trade-offs sind ja schon beschrieben worden. Wer kann, der trifft im Einzelfall eine qualifizierte Entscheidung, alle anderen benutzen die mitgelieferten Komponenten und fahren im Regelfall nicht schlecht damit.

Ich wollte eigentlich damit nur sagen, daß "echte" Listen eine Berechtigung haben.

@Hansa: wie sieht es mit dem Link aus?

[Robert_G]

Das Kopieren von dyn. Arrays lässt sich durch Containerklassen (wie zum Beispiel Tist) minimieren, aber es bleibt trotzdem bestehen.
Ich muss mich jetzt mal als ein Fan von Liten outen. Es ist ungemein praktisch wenn ich einfach hinter Element X einen neuen Knoten einfügen kann, ohne dass sich für die anderen Knoten etwas ändert. Wenn man sowieso nur durch den Container iterieren will, ist das eine elegante, feine Lösung. ;)
Es gibt auch modernere Ansätze wie die Skiplist. Ddurch kann man ehr schnell in so einem Container suchen, bzw. sortiert einfügen. :)

@mael
Schnieke Iterierung für Listen ist ab D2005 durch for in möglich. ;)