Warum ist das löschen in einer einfach verkettete Liste O(1)?

Ich nicht ruhig verstehen, warum das löschen am Ende eine einfach verkettete Liste geht in O(1) Zeit, als die wikipedia-Artikel sagt.

Eine einfach verkettete Liste besteht aus Knoten. Ein Knoten enthält eine Art von Daten, und eine Referenz auf den nächsten Knoten. Die Referenz der Letzte Knoten in der verketteten Liste, ist null.

--------------    --------------           --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
--------------    --------------           --------------

Ich zwar entfernen kann, der den letzten Knoten in O(1). Aber in diesem Fall nicht die Referenz des neu letzten Knoten der vorherigen, auf null, da es immer noch enthält die Referenz auf die gelöschte letzten Knoten. So Frage ich mich, tun, Sie vernachlässigen, dass in der Laufzeit-Analyse? Oder ist es consired dass Sie nicht haben, um das zu ändern, da sich der Verweis, gut, nur Punkte, nichts, und so gesehen wird als null?

Weil wenn wäre es nicht vernachlässigt werden, würde ich argumentieren, dass mit dem löschen ist O(n). Da muss man iteriert über die gesamte Liste zu bekommen, um den neu letzten Knoten und setzen Sie den Verweis auch auf null. Nur in einer doppelt verketteten Liste, es wäre wirklich O(1).

- - edit - -
Vielleicht ist diese Sichtweise gibt einige mehr ausräumen. Aber ich finden Sie unter "löschen eines Knotens" als erfolgreich löschen der Knoten selbst und der Einstellung der vorherigen Verweis auf null.

InformationsquelleAutor der Frage WG- | 2012-12-27

  1. 28

    Ich bin nicht sicher, ich sehe im Wikipedia-Artikel, wo es heißt, dass es möglich ist, zu entfernen, der Letzte Eintrag für eine einfach-verkettete Liste in O(1) Zeit, aber diese information ist falsch, in den meisten Fällen. Einen einzelnen Knoten in einer verketteten Liste, es ist immer möglich, entfernen Sie den Knoten, nachdem es in O(1) Zeit, durch Neuverkabelung die Liste um, dass neue Knoten. Also, wenn Sie einen Zeiger auf den letzten Knoten in einer verketteten Liste, dann könnte man löschen wird das Letzte element der Liste in O(1) Zeit.

    Jedoch, wenn Sie nicht irgendwelche extra Zeiger in der Liste andere als ein head-Zeiger ist, dann konnte man Sie nicht löschen wird das Letzte element der Liste, ohne Scannen, um das Ende der Liste, die verlangen, Θ(n) Zeit, als Sie es bemerkt haben. Sie sind absolut richtig, dass nur das löschen des letzten Knotens, ohne zuerst das ändern der Zeiger in es wäre eine Sehr Schlechte Idee, da wenn Sie dies tun, wird die vorhandene Liste enthalten würde, ein Zeiger auf ein Objekt freigegeben.

    Mehr in der Regel - die Kosten für eine Einfüge-oder Löschvorgang in eine einfach-verkettete Liste O(1), vorausgesetzt, Sie haben einen Zeiger auf den Knoten direkt vor der Sie einfügen möchten, oder löschen. Allerdings müssen Sie möglicherweise zusätzliche arbeiten (bis zu Θ(n)) zu finden, die Knoten.

    Hoffe, das hilft!

    InformationsquelleAutor der Antwort templatetypedef

  2. 7

    Die addition/Löschung von ALLE Knoten an ALLE Lage ist O(1). Code spielen Sie einfach mit der fixen Kosten (paar Hinweise, Berechnungen und malloc/befreit) hinzufügen/löschen der Knoten. Dieser rechnerische Kosten behoben wird, die für jeden speziellen Fall.

    Jedoch, die Kosten zu erreichen(Indexierung) der gewünschte Knoten ist O(n).

    Dem Artikel ist lediglich die Auflistung der addition/deletion in mehrere sub-Kategorien(hinzufügen in der Mitte, Anfang, Ende), um zu zeigen, dass die Kosten für das hinzufügen in der Mitte unterscheidet sich als Zugabe in Beginn/Ende (Aber die entsprechenden Kosten sind noch fest).

    InformationsquelleAutor der Antwort

  3. 0

    Beispielsweise können Sie einen Zeiger auf das element vor dem letzten ("second end") und beim löschen:
    1. Löschen *neben dieser "zweiten vom Ende" - element.
    2. Setzen Sie diese "zweite vom Ende," *weiter auf NULL

    InformationsquelleAutor der Antwort Horuss

  4. 0

    Wenn Sie einschließlich der Kosten für die Behebung des dangling node, können Sie immer noch in O(1) mit dem Einsatz der sentinel-node für das Ende (auch beschrieben auf dieser Seite).

    Ihre "leere" Liste beginnt mit einem einzelnen sentinel

    Head -> [Sentinel]

    Fügen Sie einige Sachen

    Head -> 1 -> 2 -> 3 -> [Sentinel]

    Nun löschen Sie den Schwanz (3) durch markieren der Knoten, der war 3 als ungültig, und dann das entfernen der link zu der alten sentinel, und die Speicherfreigabe für Sie:

    Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel]

    InformationsquelleAutor der Antwort James

  5. 0

    O(1) bedeutet einfach "Konstanten Kosten". Es bedeutet nicht 1-Betrieb. Es heißt "am meisten "C" - Operationen mit C fest eingestellt, unabhängig von anderen Parametern ändern (wie Liste Größe). In der Tat, in die manchmal verwirrende Welt der big-Oh: O(1) == O(22).

    Dagegen löschen die gesamte Liste ist O(n) Kosten, weil der Preis ändert sich mit der Größe (n) der Liste.

    InformationsquelleAutor der Antwort user268396

  6. 0

    Für die Zukunft, ich muss sagen, nach einigen Recherchen fand ich, dass keines der Argumente in der Antwort auf diese Frage relevant sind. Die Antwort ist, dass wir einfach entscheiden, für die Spitze des stack zu sein, der Kopf der verketteten Liste (eher als der Schwanz). Dies stellt eine leichte Veränderung in der push-routine, aber dann die pop-und push wird, bleiben beide o(1).

    InformationsquelleAutor der Antwort Negar

  7. 0

    Wenn Sie geben einen Zeiger auf den Knoten, die gelöscht werden, in eine einfach verkettete Liste, dann können Sie Sie löschen dieses Knotens in konstanter Zeit, indem Sie einfach kopieren, den nächsten Knoten auf die Knoten, die gelöscht werden.

    M pointer to node to delete
M.data=M.next.data
M.next=M.next.next

    Sonst, wenn Sie benötigen, zu suchen den Knoten, dann können Sie nicht tun besser als O(n)

    InformationsquelleAutor der Antwort yamenk

  8. 0

    Ja, Sie können dies tun, in O(1) Zeit, selbst wenn Sie nicht pflegen einen Zeiger auf die "Vorherige element".

    Lassen Sie uns sagen, Sie haben diese Liste, wo "Kopf" und "Schwanz" sind statische Zeiger, und "Ende" wird ein Knoten markiert, als ein Ende. Sie können mit "next == NULL" als normal, aber in diesem Fall müssen Sie ignorieren den Wert:

    head -> 1 -> 2 -> 3 -> 4 -> 5 -> End <- tail

    Nun, erhält man einen Zeiger auf Knoten 3, aber nicht den vorherigen Knoten. Sie haben die head-und tail-Zeiger zu. Hier sind einige python-ish-code, vorausgesetzt, dass eine Klasse SingleLinkedList.

    class SingleLinkedList:

    # ... other methods

    def del_node(self, node):  # We "trust" that we're only ever given nodes that are in this list.
        if node is self.head:
            # Simple case of deleting the start
            self.head = node.next
            # Free up 'node', which is automatic in python
        elif node.next is self.tail
            # Simple case of deleting the end. This node becomes the sentinel
            node.value = None
            node.next = None
            # Free up 'self.tail'
            self.tail = node
        else:
            # Other cases, we move the head's value here, and then act
            # as if we're deleting the head.
            node.value = self.head.value
            self.head = self.head.next
            new_head = self.head.next
            # Free up 'self.head'
            self.head = new_head

    Ach, das verschiebt die Liste und bewegt-Werte um, die möglicherweise oder möglicherweise nicht gut für Ihre Anwendung.

    InformationsquelleAutor der Antwort Chris Cogdon

Schreibe einen Kommentar