Doppelt verkettete Liste?
Hi,
ich verstehe nicht, warum das Entfernen eines Elements in einer doppelt verketteten Liste in der Laufzeit O(1) geschehen kann und nicht, wie bei einer einfach verketteten Liste nur in O(n).
Wenn ich bei einer doppelt verketteten Liste das letzte Element entfernen möchte, müsste ich doch auch über alle Vorgänger iterieren. Genau so wie bei einer einfach verketteten Liste, oder nicht?
1 Antwort
Vom Beitragsersteller als hilfreich ausgezeichnet
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Computer
Hi,
wenn du den Anfang a und das Element x zum Entfernen hast, musst du bei einer einfach verketteten Liste
i = anf;
while(i.next!=x) i=i.next; //O(n)
i.next = i.next.next;
machen, um das Element zu entfernen. Hast du eine doppelt verkettete Liste, musst du nur
x.prev.next = x.next;
x.next.prev = x.prev;
machen, um das Element zu entfernen, und daher nicht die ganze Liste durchgehen.
Woher ich das weiß:Berufserfahrung – Softwareentwickler & Admin