Verkettete Liste einfügen Laufzeit Verwirrung
Ich habe versucht, um zu bestätigen, die Laufzeit für das einfügen für verkettete Listen und es scheint, wie es gibt zwei verschiedene Antworten.
Einfügen eines Elements am Ende einer verketteten Liste, ich würde denken, dass es dauern O(n), da es zu durchqueren, um das Ende der Liste, um Zugriff auf den Schwanz. Aber einige der Antworten, die ich gesehen habe, sagt O(1)? Sind Sie der Annahme, dass alle verknüpfte Listen-Implementierung ein Zeiger auf den Schwanz? Wenn ja, ist dies eine akzeptable Annahme?
Zweiten, einige Plätze auch darauf hin, dass beim einfügen eines Elements in der Mitte einer verknüpften Liste ist O(1), die ich bin verwirrt, etwa aufgrund der gleichen Argumentation der traverse in die Mitte der Liste, um es einzufügen.
Könnte jemand bitte klären? Danke.
- Wenn die insertion in der Mitte der Liste O(1) wir müssten keine arrays mehr :).
- Li0liQ: Einer der Vorteile von verketteten Listen ist, dass Sie können Elemente einfügen, die in der Mitte in konstanter Zeit, wo in arrays, die Sie benötigen, um alle der folgenden Elemente.
- Was über die ständige Indizierung?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einfügen in eine verkettete Liste O(1) wenn Sie einen Zeiger auf den Knoten, wo Sie möchten, legen Sie das Element. Finden dieser Knoten kann in O(n) je nachdem, was Sie tun möchten.
Wenn Sie halten einen Zeiger auf die Liste in den Schwanz, dann brauchen Sie nicht, um es zu suchen und dann einfügen O(1).
Und Nein, nicht alle Implementierungen verkettete Liste einen Zeiger auf das Ende der Liste.
Beispiel
Angenommen, Sie haben eine leere Liste, auf die Sie fügen Sie einen einzelnen Knoten,
x. Dann fügen SienKnoten, um die Liste vor und nachx. Sie können immer noch einfügen eines einzelnen Knoten nachxindem Sie einfach die Aktualisierung IhrernextZeiger (und der neue Knoten ist), unabhängig davon, wie viele Knoten sind waren der Liste.Änderungen an verlinkten Liste betrifft zwei Operationen:
In der Verlinkten Liste, die zweite operation ist eine
O(1)Betrieb, so ist es eine Frage der Kosten für die ersten Operationen.Beim anfügen an den letzten Knoten, naiven Implementierungen der verknüpften Liste führen würde
O(n)iteration Zeit. Aber gut verlinkte Liste Bibliotheken berücksichtigen die häufigsten Anwendungen und speziellen Fall Zugriff auf den letzten Knoten. Diese Optimierung führen würde, inO(1)Abruf des letzten Elements, was insgesamt zuO(1)Einfügung Zeit zu Ende.Als für die Mitte, Ihre Analyse ist richtig, dass die Lokalisierung der Knoten würde auch
O(n). Allerdings haben einige Bibliotheken setzen eine Methode, die ein Zeiger auf, wo der neue Knoten eingefügt werden soll, anstatt den index (z.B.C++list). Dies beseitigt die linearen Kosten, was über alleO(1).Während der insertion auf die Mitte ist in der Regel gedacht, als
O(n)Betrieb kann optimiert werden, umO(1)in einigen Fällen. Das ist das Gegenteil von array-Liste, wo die insertion operation selbst (zweite operation) istO(n), als alle Elemente in höhere Lagen müssen verlegt werden. Dieser Vorgang kann optimiert werden.Für die insertation
Eine naive Implementierung einer verknüpften Liste führen würde
O(n)einlegen Zeit. Aber gut verlinkte Liste, Bibliothek Schriftsteller würde eine Optimierung für die gängigen Fälle, so würden Sie einen Verweis auf die letzten Elemente (oder haben eine kreisförmig verkettete Liste-Implementierung), die eineO(1)einlegen Zeit.Als für die Einfügung in die Mitte. Einige Bibliotheken, wie die, dass der
C++hat eine vorgeschlagene Standort für die insertion. Würden Sie einen Zeiger auf die Liste der Knoten, wo der neue angehängt werden. Solche Einfügungen Kosten würdeO(1). Ich glaube nicht, dass Sie erreichen könnenO(1)von index-Nummer.Dies ist adaptiert, um eine array-Liste, wo einfügen, um die mittleren Kräfte Neuanordnung aller Elemente höher als es, so hat es ein
O(n)Betrieb.Wenn Sie nicht mutieren die Knoten des (einfach) verkettete Liste, Sie brauchen O(n) Zeit einfügen an einer beliebigen position in der Liste (weil Sie kopiert werden muss, um alle Knoten vom Anfang der Liste, um die position des neuen Elements. Es ist O(1) für eine veränderbare Liste, wenn Sie bereits einen Zeiger auf den Knoten, wo Sie möchten, um ein Element einfügen, und O(n), wenn Sie haben, um ihn zu suchen.
In beiden Fällen müssen Sie nur O(1) Zeit, die zum einfügen eines Elements am Anfang der Liste. Wenn Sie oft brauchen, um ein element einzufügen, in der Mitte der Liste (O(n) Fall), Sie sollten eine andere Struktur der Daten.
Pro Java LinkedList-source-code, Java erreicht der O(1) für
LinkedListSchwanz Operationen, indem Sie dieheader- Eintrag einen link zu dem tail-element überheader.previous. Wenn Sie So wollen, das Letzte element die Klasse kann immer wiederheader.previous, so dass für eine Konstante Zeit.Ich davon ausgehen, dass viele andere Sprachen verwenden die gleiche grundlegende Strategie.
Offensichtlich hast du wahrscheinlich schaute auf den wikipedia-Eintrag http://en.wikipedia.org/wiki/Linked_list. Ich sehe die Tabelle, wo Sie angeben, dass sowohl das einfügen/löschen am Ende und in der Mitte der Liste O(1) Leistung aber nicht zu erarbeiten, wie Sie bestimmt, dass.
Gibt es einige interessante Antworten auf eine ähnliche Frage hier auf stackoverflow auf Warum ist das einfügen in der Mitte einer verketteten Liste O(1)?. Das original-poster der Frage editierte seinen Beitrag und machte einen Punkt, dass er glaubt, wenn man sagt, dass beim einfügen/löschen O(1) Sie reden von der eigentlichen insert-operation und nicht die Suche nach, wo Sie legen Sie auf. Das macht Sinn, aber ich habe nicht gesehen, dass die formal erklärte, in keinem der Artikel die ich gefunden habe, an dieser Stelle.
Ich denke, ein Grund für Ihre Verwirrung ist die Tatsache, dass Sie denken, als wenn es eine ideale/kanonische Link-Liste, die man entweder hat oder nicht bestimmte Kopf - /Schwanz-Zeiger. Die Realität ist, dass jede lineare (d.h. keine Verzweigung) Daten-Struktur, die greift auf Elemente über Zeiger aus der vorherigen Elemente ist im Grunde eine verknüpfte Liste. Ob Sie halten Zeiger auf das erste, Letzte k-TEN usw. Elemente ist völlig bis zu Ihnen. Also, wenn Sie brauchen eine Liste, wo Sie Häufig benötigen, einfügen/löschen von Elementen an der 10-position, können Sie einfach umsetzen, die hat einen extra Zeiger auf das 9. element und das nicht in O(1) Zeit.
Andere Sache ist, dass bei der Iteration über die Elemente einer verketteten Liste, können Sie fügen Sie ein neues element direkt nach dem aktuellen element (und nur vor, wenn eine doppelt verkettete Liste) in O(1), da Sie bereits über einen Zeiger auf diesen.
Als @Kaleb Brasee weist darauf hin, einlegen am Heck in Java ist O(1), denn Java verwendet eine doppelt verknüpfte Liste, als seine
LinkedListUmsetzung. Ich denke, das ist eine relativ häufige Wahl für viele SDK-Implementierungen. Zum Beispiel die STL -listUmsetzung ist doppelt verknüpfte (Quelle).