Ich habe versucht, die Laufzeit für die Einfügung für Linked List zu bestätigen, und es scheint, als gäbe es zwei verschiedene Antworten.
Zum Einfügen eines Elements am Ende einer Verknüpfungsliste würde ich annehmen, dass es O (n) erfordern würde, da es bis zum Ende der Liste durchlaufen werden muss, um auf das Ende zuzugreifen. Aber einige der Antworten, die ich gesehen habe, sagen O (1)? Nehmen sie an, dass alle verketteten Listen die Implementierung eines Zeigers auf den Schwanz haben? Wenn ja, ist das eine akzeptable Annahme?
Zweitens schlagen einige Stellen auch vor, dass das Einfügen eines Elements in der Mitte einer verknüpften Liste O (1) ist, worüber ich wegen der gleichen Argumentation von quer durch die Mitte der Liste verwirrt bin, um es einzufügen.
Könnte jemand bitte klarstellen? Danke.
Das Einfügen in eine verknüpfte Liste ist O (1), wenn Sie einen Zeiger auf den Knoten haben, in den Sie das Element einfügen möchten. Finden dieser Knoten kann O (n) abhängig von dem sein, was Sie tun möchten.
Wenn Sie einen Zeiger auf den Schwanz der Liste halten, müssen Sie nicht danach suchen, und dann wird O (1) eingefügt.
Und nein, nicht alle Implementierungen von verknüpften Listen haben einen Zeiger auf das Ende der Liste.
Beispiel
Angenommen, Sie haben eine leere Liste, zu der Sie einen einzelnen Knoten hinzufügen, x . Dann fügen Sie n nodes zur Liste vor und nach x hinzu. Sie können immer noch einen einzelnen Knoten nach x einfügen, indem Sie einfach den next -Zeiger (und den des neuen Knotens) aktualisieren, unabhängig davon, wie viele Knoten die Liste sind.
Änderungen an der verknüpften Liste umfassen zwei Operationen:
In der verknüpften Liste ist die zweite Operation eine Operation O(1) , es handelt sich also um die Kosten der ersten Operationen.
Beim Anhängen an den letzten Knoten würden naive Implementierungen der verknüpften Liste in O(n) Iterationszeit resultieren. Gute Bibliotheken mit verknüpften Listen würden jedoch für die häufigsten Verwendungen und Sonderfälle für den Zugriff auf den letzten Knoten verantwortlich sein. Diese Optimierung würde zu einem O(1) Abruf des letzten Elements führen, was dazu führt, dass die gesamte O(1) Einfügungszeit zu Ende geht.
Was die Mitte anbelangt, ist Ihre Analyse insofern korrekt, als das Auffinden des Knotens auch O(n) erfordert. Einige Bibliotheken stellen jedoch eine Methode zur Verfügung, bei der anstelle des Index ein Zeiger auf den neuen Knoten verwendet wird (z. B. C++ list ). Dies eliminiert die linearen Kosten, die über% O(1) ergeben.
Während die Einfügung in die Mitte normalerweise als O(n) Operation betrachtet wird, kann sie in manchen Fällen auf O(1) optimiert werden. Dies ist das Gegenteil der Array-Liste, bei der die Einfügeoperation selbst (die zweite Operation) O(n) ist, da alle Elemente an höheren Positionen verlagert werden müssen. Dieser Vorgang kann nicht optimiert werden.
Zum Einfügen
Eine naive Implementierung einer verknüpften Liste würde zu O(n) Einfügungszeit führen. Schreiber von gut verlinkten Listenbibliotheken würden jedoch für die häufigsten Fälle optimieren, so dass sie einen Verweis auf die letzten Elemente behalten (oder eine zirkuläre verkettete Listenimplementierung haben), was zu einer O(1) -Einfügungszeit führt.
Wie für die Einfügung in die Mitte. Einige Bibliotheken wie die von C++ haben einen vorgeschlagenen Speicherort zum Einfügen. Sie würden einen Zeiger auf den Listenknoten nehmen, an den der neue angehängt werden soll. Solche Einfügungen würden O(1) kosten. Ich glaube nicht, dass Sie O(1) anhand der Indexnummer erreichen können.
Dies liegt an einer Array-Liste, bei der die Einfügung in die mittleren Kräfte alle Elemente, die höher sind, neu anordnet, also muss es eine Operation O(n) sein.
Wenn Sie die Knoten Ihrer (einfach) verknüpften Liste nicht mutieren, müssen Sie O (n) Zeit an einer beliebigen Position in der Liste einfügen (weil Sie alle Knoten vom Anfang der Liste kopieren müssen) an der Position des neuen Elements: Es ist O (1) für eine veränderbare Liste, wenn Sie bereits einen Zeiger auf den Knoten haben, an dem Sie ein Element einfügen möchten, und O (n), wenn Sie danach suchen müssen. In beiden Fällen benötigen Sie nur O (1) Zeit, um ein Element am Anfang der Liste einzufügen. Wenn Sie häufig ein Element in die Mitte der Liste einfügen müssen (O (n) -Fall), sollten Sie eine andere Datenstruktur verwenden.
Mit dem Java LinkedList-Quellcode erreicht Java den O (1 ) für LinkedList Tail-Operationen, indem Sie dem header -Eintrag über header.previous eine Verbindung zum Tail-Element geben. Wenn Sie also das letzte Element wollen, kann die Klasse immer header.previous zurückgeben, was eine konstante Zeit ermöglicht.
Ich nehme an, dass viele andere Sprachen die gleiche grundlegende Strategie verwenden.
Offensichtlich haben Sie sich wahrscheinlich den Wikipedia-Eintrag Ссылка angesehen. Ich sehe in der Tabelle, wo sie angeben, dass sowohl das Einfügen / Löschen am Ende als auch in der Mitte der Liste eine O (1) -Leistung haben, aber nicht näher erläutern, wie sie das bestimmt haben.
Es gibt einige interessante Antworten auf eine ähnliche Frage hier auf stackoverflow bei Warum wird in der Mitte einer verknüpften Liste O (1) eingefügt? . Das ursprüngliche Poster dieser Frage editierte seinen Beitrag und machte einen Punkt, den er glaubt, wenn gesagt wird, dass das Einfügen / Löschen O ist (1) sie sprechen über die tatsächliche Einfügeoperation und nicht über das Finden, wo eingefügt werden soll. Das macht Sinn, aber ich habe nicht gesehen, dass das in irgendeinem der Artikel, die ich an diesem Punkt gefunden habe, formell erwähnt wurde.
Ich denke, ein Grund für Ihre Verwirrung ist die Tatsache, dass Sie denken, dass es eine ideale / kanonisch verknüpfte Liste gibt, die entweder bestimmte Head / Tail-Zeiger hat oder nicht. Die Realität ist, dass jede lineare (d. H. Keine Verzweigung) Datenstruktur, die auf Elemente zugreift, indem sie Zeiger von vorherigen Elementen durchläuft, im Grunde eine verkettete Liste ist. Ob Sie Hinweise auf die ersten, letzten, k-ten usw. Elemente behalten, liegt ganz bei Ihnen. Wenn Sie also eine Liste benötigen, in der Sie häufig Elemente an der 10. Stelle einfügen / löschen müssen, können Sie einfach eine mit einem zusätzlichen Zeiger auf das 9. Element implementieren und dies in O (1) -Zeit tun.
Eine andere Sache ist, dass wenn Sie über die Elemente einer verknüpften Liste iterieren, Sie ein neues Element direkt nach dem aktuellen Element (und kurz davor, wenn es sich um eine doppelt verkettete Liste handelt) in O (1) einfügen, weil Sie bereits habe einen Zeiger darauf.
Wie @ Kaleb Brasee hervorhebt, ist das Einfügen am Ende in Java O (1), da Java eine doppelt verknüpfte Liste als LinkedList Implementierung verwendet. Ich denke, das ist eine ziemlich häufige Wahl für viele SDK-Implementierungen. Zum Beispiel ist die STL list Implementierung doppelt verlinkt ( Quelle ).
Tags und Links algorithm language-agnostic big-o