Algorithmen[3]#2

[localhorst]

welche vorteile die kombiniert werden sollen meinen die? push, pop € O(1) von listen.. und von uarray? platzkomplexität ist imo bei beiden in O(n)..

[ryo]

Das wüsste ich auch gerne. Es geht doch um die Implementierung eines "Stack" - was nützt mir hier der freie Zugriff eines Array? Ein Stack arbeitet doch rein nach dem FILO Prinzip...

[markusj]

Array: Schneller wahlfreier Zugriff
Liste: Schnelles einfügen und entfernen auch bei größeren Datenmengen ohne unnötige Kopieroperationen.

mfG
Markus

[salami]

Aber diese Vorteile sind bei einem Stack ja eigentlich egal, da man da nur das oberste Element auf dem Stapel verwenden kann.
Deshalb wird auch mir nicht ganz klar, welche Vorteile des Arrays man da einbauen soll. Die Liste müsste doch schon die schnellste Methode sein, die wir bisher kennen gelernt haben.

[Christian S.]

Aber diese Vorteile sind bei einem Stack ja eigentlich egal, da man da nur das oberste Element auf dem Stapel verwenden kann.
Deshalb wird auch mir nicht ganz klar, welche Vorteile des Arrays man da einbauen soll. Die Liste müsste doch schon die schnellste Methode sein, die wir bisher kennen gelernt haben.

Sehe ich genauso. Hat da jemand einen Tipp was für Vorteile einem denn bei einer Liste abhanden gehen?
Edit: Jeder Listeneintrag soll ein festes Array mit k Elementen enthalten und kein unbounded array, wenn ich das richtig sehe. Somit geht es bei dem Vereinigen wohl nicht um den Aufwand der Operationen, sondern um einen anderen wesentlichen Vorteil von Arrays. Vergleicht mal die Definition der Listenitems mit Arrayelementen.

[fredpape]

Arrayitems? Sind in Arrays nicht direkt die Elemente gespeichert? oO
Ich frag mich, ob wir bei diesem Beispiel jetzt irgendeine aromortisierte Laufzeit etc. zeigen sollen. Ich hoffe mal nicht

[Christian S.]

Arrayitems? Sind in Arrays nicht direkt die Elemente gespeichert? oO

Eben. Der Vorteil muss ja nichts mit der Laufzeit zu tun haben.

[Tankwart]

Kann ich bei der b) das überhaupt in Abhängigkeit von n bzw. K schreiben? Bei meinen Methoden mit einem Handle, welches das aktuelle Element des Arrays speichert, brauch ich eig nur konstante Zeit.

[localhorst]

wth welchen vorteil?? doch platz? das ist ja wie gesagt imo kein wirklicher vorteil

[Tankwart]

Was mir grad auch noch auffällt: Gilt die Schnittstelle in der c) für die ganze Aufgabe?
Hab a) & b) jetzt von Hand implementiert, aber wenn man die Schnittstelle benutzen darf könnt ich ja einfach mit dem splice() arbeiten.