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 von
marabu:
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 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?