Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Lösch-Aufwand aus einfach-/doppelt verketteten Listen
Hallo,
Warum haben das Löschen aus einfachen und aus doppelt verketteten Listen einen unterschiedlichen Aufwand?
Müsste ich nicht bei beiden mit einem Aufwand von O(n) erstmal an die Stelle des Elements in der Liste gelangen, bevor ich es mit O(1) dann löschen kann?
Liebe Grüße
Speedy
Das ist etwas Tricky… Gemeint ist, dass du schon einen zeiger auf das Element hast, dass du löschen willst.
Bei einer einfach verketteten Liste musst du dann den Vorgänger dieses Elements suchen um dessen Nachfolger auf das Element hinter dem zu löschenden zu setzen.
Bei einer doppelt verketteten Liste musst du den Vorgänger nicht suchen, da eine Referenz auf ihn schon im zu löschenden Element vorhanden ist.
Danke dir, Destranix!