Verknüpfte Liste Einfügen Laufzeit Verwirrung

Question

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.

Für das Einfügen eines Elements am Ende einer Verknüpfungsliste würde ich denken, dass es O (n) dauern würde, da es bis zum Ende der Liste durchlaufen 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 empfehlen einige Stellen auch, dass das Einfügen eines Elements in der Mitte einer verketteten 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? Vielen Dank.

Answer 1

In eine verkettete Liste einfügen ist O (1), wenn Sie einen Zeiger auf den Knoten haben, in den Sie das Element einfügen möchten. Finding dieser Knoten kann O (n) je nachdem, 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 verketteten Listen-Implementierungen haben einen Zeiger auf das Ende der Liste.

Beispiel

Sie eine leere Liste haben Nehmen wir an, die Sie einen einzelnen Knoten hinzufügen, x. Dann fügen Sie n Knoten der Liste vor und nach x hinzu. Sie können immer noch einen einzelnen Knoten nach x einfügen, indem Sie einfach den Zeiger (und den neuen Knoten) aktualisieren, unabhängig davon, wie viele Knoten die Liste sind.

Answer 2

Änderungen an verlinkten Liste zwei Operationen beinhalten:

1. den Knoten Auffinden des neuen Knotens zu
2. tatsächlich den Knoten anhängen anhängen, indem Sie die Knoten Zeiger ändert

In verlinkte Liste, die zweite Operation ist eine O(1) Operation, so dass es sich um die Kosten der ersten Operationen handelt.

Beim Anhängen an den letzten Knoten würden naive Implementierungen der verknüpften Liste die Iterationszeit O(n) ergeben. 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 O(1) Abruf des letzten Elements führen, was insgesamt zu O(1) Einfügungszeit enden würde.

Wie für die Mitte ist Ihre Analyse korrekt, in der Ortung des Knotens würde auch O(n). Bei einigen Bibliotheken wird jedoch eine Methode verfügbar gemacht, bei der anstelle des Index ein Zeiger auf den neuen Knoten verwendet wird (z. B. C++list). Dies eliminiert die linearen Kosten, die sich über alle O(1) ergeben.

Während das Einfügen in die Mitte normalerweise als O(n) Betrieb betrachtet wird, kann es in einigen 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 verketteten Liste würde O(n) Insertionszeit ergeben. Allerdings würden gute Listenbibliotheksverfasser 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 Einfügungszeit von O(1) führt.

Wie für die Einfügung in die Mitte. Einige Bibliotheken wie die von C++ haben einen vorgeschlagenen Ort 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) per Index erreichen können.

Dies ist eine Array-Liste, wo Einfügen in die mittleren Kräfte Neuordnung aller Elemente höher als es ist, so muss es eine O(n) Operation sein.

Answer 3

Per the Java LinkedList source code erreicht Java den O (1) für LinkedList tail Operationen über den header.previousheader Eintrag eine Verknüpfung zu dem Schwanzelement ergibt. Wenn Sie also das letzte Element wollen, kann die Klasse immer header.previous zurückgeben, was eine konstante Zeit erlaubt.

Ich nehme an, dass viele andere Sprachen die gleiche Grundstrategie verwenden.

Answer 4

Offensichtlich haben Sie wahrscheinlich den Wikipedia-Eintrag http://en.wikipedia.org/wiki/Linked_list angesehen. Ich sehe die Tabelle, wo sie angeben, dass sowohl Einfügen/Löschen vom 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 Why is inserting in the middle of a linked list O(1)?. Das ursprüngliche Poster dieser Frage editierte seinen Beitrag und machte einen Punkt, den er glaubt, wenn es 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.

Answer 5

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 auf die Position des neuen Elements Es ist O (1) für eine veränderbare Liste, wenn Sie bereits einen Zeiger auf den Knoten haben, in den Sie ein Element einfügen möchten, und O (n), wenn Sie danach suchen müssen In beiden Fällen benötigen Sie nur eine (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) case), sollten Sie andere Daten verwenden Struktur

Answer 6

Ich denke, ein Grund für Ihre Verwirrung ist die Tatsache, dass Sie denken, als ob es eine ideale/kanonische verknüpfte Liste gibt, die entweder hat oder tut nicht bestimmte Head/Tail-Zeiger haben. 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 hinter dem aktuellen Element einfügen können (und kurz davor, wenn es sich um eine doppelt verkettete Liste handelt) in O (1), weil Sie habe schon einen Zeiger darauf.

Answer 7

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 verknüpft (source).