Guten Tag! Danke fürs tolle Video! Ich verstehe übrigens den Unterschied zwischen random access a[i] und dem Traversieren mithilfe eines Iterators nicht ganz.. Warum ist bei random Access die Laufzeit O(n) und im Fall von iterator hingegen O(1)? Vielen Dank im Voraus ^^
Stellen Sie sich vor, Sie haben eine Liste a mit 2000 Elementen, und jemand möchte von Ihnen das Element a[1000] aus der Mitte haben. Dann können Sie bei einer verketteten Liste nichts anderes tun, als sich von einem Ende der Liste aus 1000 Elemente bis zur Mitte durchzuhangeln - das dauert Zeit O(n). Wenn Sie aber ohnehin vorhaben, die Listenelemente der Reihe nach durchzugehen, dann können Sie 2000 Listenelemente zum Preis von 2000 mal "gehe zum nächsten Element" anschauen, d.h. pro Listenelement ist der Aufwand nur O(1).
@@Gogol-Doering verstehe. Statt jedes Mal von Anfang anzufangen merkt man sich einen Iterator wenn die ganze Liste durchzulaufen ist. Wenn man aber eine remove methode implementieren würde, würde das trotzdem die Laufzeit O(n) haben, egal ob man random access oder einen Iterator benutzt, oder? Vielen Dank und Liebe Grüße.
Ein Kommentar für den Algorithmus. :)
Ein Kommentar für den Kommentar ;-p
Merci
Guten Tag! Danke fürs tolle Video! Ich verstehe übrigens den Unterschied zwischen random access a[i] und dem Traversieren mithilfe eines Iterators nicht ganz.. Warum ist bei random Access die Laufzeit O(n) und im Fall von iterator hingegen O(1)? Vielen Dank im Voraus ^^
Stellen Sie sich vor, Sie haben eine Liste a mit 2000 Elementen, und jemand möchte von Ihnen das Element a[1000] aus der Mitte haben. Dann können Sie bei einer verketteten Liste nichts anderes tun, als sich von einem Ende der Liste aus 1000 Elemente bis zur Mitte durchzuhangeln - das dauert Zeit O(n). Wenn Sie aber ohnehin vorhaben, die Listenelemente der Reihe nach durchzugehen, dann können Sie 2000 Listenelemente zum Preis von 2000 mal "gehe zum nächsten Element" anschauen, d.h. pro Listenelement ist der Aufwand nur O(1).
@@Gogol-Doering verstehe. Statt jedes Mal von Anfang anzufangen merkt man sich einen Iterator wenn die ganze Liste durchzulaufen ist. Wenn man aber eine remove methode implementieren würde, würde das trotzdem die Laufzeit O(n) haben, egal ob man random access oder einen Iterator benutzt, oder? Vielen Dank und Liebe Grüße.
10:35 hab ich nicht schon a.last in el.prev reingeschoben?
Also waere object(a.last) dann nicht die falsche Stelle? Oder is deshalb das next dran
Nein, a.last wird erst später umgesetzt, ab 10:59
@@Gogol-Doering Dankeschön!