Algorithmus zum Löschen eines Elements in einer einzelnen verketteten Liste mit O (1) -Komplexität

8

Ich bin Informatikstudent in Deutschland. Mein Professor nutzte die folgende Frage zum Nachdenken:

'Eine Referenz auf einen Knoten in einer einzelnen verknüpften Liste gegeben (der nicht der letzte Knoten ist). Geben Sie einen Algorithmus an, um dieses Element aus der Liste zu löschen, die O (1) -Komplexität aufweist, während die Integrität beibehalten wird.

Ich habe darüber nachgedacht, aber ich bin mir ziemlich sicher, dass es keinen solchen Algorithmus gibt. Da es sich um eine einzelne verknüpfte Liste handelt, müssen Sie jeden Knoten in der Liste durchlaufen, bis Sie den Knoten erreichen, der gelöscht werden soll, da Sie den nächsten Zeiger im Knoten vor dem Löschen ändern müssen. Was zu O (n) Komplexität führen würde.

Vermisse ich etwas?

    
Martin Thurau 27.04.2009, 15:07
quelle

6 Antworten

24

Es hängt davon ab, ob die Knoten änderbar sind (im Wert).

There ist eine Möglichkeit dies zu tun, wenn Sie mit den Knoten tun können, was Ihnen gefällt:

%Vor%

Alle Informationen von toDelete wurden nun durch die Informationen in der alten toDelete.next überschrieben. (Abhängig von der Plattform müssen Sie dann eventuell das alte toDelete.next freigeben - was bedeutet, dass Sie einen temporären Verweis darauf haben. Nicht gut, wenn jemand sonst noch einen Verweis darauf hat. In Java / C # würden Sie einfach ignoriere es.)

Ich habe versucht, einen Weg zu finden, darauf hinzuweisen, ohne es zu verraten, aber es ist ein bisschen schwierig ...

Es ist jedoch darauf angewiesen, dass dies nicht der letzte Knoten in der Liste ist.

    
Jon Skeet 27.04.2009, 15:12
quelle
8

Das Löschen eines Knotens wird nicht genau betrachtet, aber Sie können die Daten des nächsten Knotens in den aktuellen Knoten kopieren und den nächsten Knoten löschen:

%Vor%     
Mehrdad Afshari 27.04.2009 15:13
quelle
3

Wenn es sich bei den Knoten um Grundstrukturen im Speicher handelt, können Sie den Inhalt des "nächsten" Knotens in den Speicherort des gelöschten Knotens kopieren und den Speicher dort freigeben, wo der "nächste" Knoten war.

    
Dmitry Brant 27.04.2009 15:13
quelle
2

Ja. Sie behalten als Iterationszeiger einen Zeiger auf den nächsten Zeiger der vorherigen Liste.

%Vor%     
Joshua 27.04.2009 15:13
quelle
2

Angenommen, Sie haben den Zeiger auf den Knoten, den Sie löschen möchten. Replizieren Sie den nächsten Wert in den aktuellen Knoten. Ersetzen Sie den aktuellen Zeiger durch den nächsten Knoten.

    
Joe 27.04.2009 15:14
quelle
2

verschiebe die Daten, nicht den Link. Sieh dir diesen anderen Thread an: Löschen von a mittlerer Knoten aus einer einzelnen verknüpften Liste, wenn der Zeiger auf den vorherigen Knoten nicht verfügbar ist

    
pomarc 27.04.2009 15:21
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie man ein zufälliges englisches Wort aus einer Liste auswählt [geschlossen]