Warum wird in der Mitte einer verknüpften Liste O (1) eingefügt?

Question

Gemäß Wikipedia article on linked lists wird das Einfügen in der Mitte einer verknüpften Liste als O (1) betrachtet. Ich würde denken, es wäre O (n). Müsstest du nicht den Knoten finden, der sich am Ende der Liste befinden könnte?

Berücksichtigt diese Analyse nicht das Finden der Knotenoperation (obwohl es erforderlich ist) und nur die Einfügung selbst?

EDIT:

verlinkte Listen haben mehrere Vorteile gegenüber Arrays. Das Einfügen eines Elements an einem bestimmten Punkt einer Liste ist eine Operation mit konstanter Zeit, während das Einfügen in ein Array möglicherweise die Hälfte der Elemente oder mehr erfordert.

Die obige Aussage ist ein wenig irreführend für mich. Korrigieren Sie mich, wenn ich falsch liege, aber ich denke, sollte die Schlussfolgerung sein:

Arrays:

• Finden der Punkt Einfügen/Löschen O (1)
• Durchführen der Einfügen/Löschen O (n)

verlinkte Listen:

• den Punkt Einfügen/Löschen O (n)
• Durchführen der Einfügen/Löschen O (1)

Ich denke, das einzige Mal, Sie würden nicht finden die Position ist, wenn Sie einige Finding gehalten Art von Zeiger darauf (wie in einigen Fällen mit dem Kopf und dem Schwanz). Wir können also nicht einfach sagen, dass verknüpfte Listen immer Arrays für Einfüge-/Löschoptionen übertreffen.

Answer 1

Sie haben Recht, der Artikel betrachtet "Indizierung" als eine separate Operation. Also ist die Einfügung selbst O (1), aber zu diesem mittleren Knoten gelangt man zu O (n).

Answer 2

Weil es keine Schleifen beinhaltet.

Einfügen ist wie:

• Einsatzelement
• Link zum vorherigen
• Link zu dem nächsten
getan

dies in jedem Fall konstant Zeit.

Folglich ist das Einfügen von n Elementen nacheinander O (n).

Answer 3

Einfügen ist O (1) sobald Sie wissen, wo Sie es hinstellen werden.

Answer 4

Nein, wenn Sie sich entscheiden, dass Sie einfügen möchten, wird angenommen, dass Sie sich bereits in der Mitte der Liste befinden.

Operationen auf verknüpften Listen werden oft so durchgeführt, dass sie nicht wirklich als generische "Liste" behandelt werden, sondern als eine Ansammlung von Knoten - denken Sie an den Knoten selbst als Iterator für Ihre Hauptschleife. Wenn Sie also durch die Liste stochern, bemerken Sie als Teil Ihrer Geschäftslogik, dass ein neuer Knoten hinzugefügt (oder ein alter gelöscht) werden muss, und Sie tun dies. Sie können 50 Knoten in einer einzigen Iteration hinzufügen.

Edit: Mann, du tippst einen zweiten Absatz ein und plötzlich bist du nicht der Ersthelfer, sondern der 5., der dasselbe sagt wie die ersten 4!

Answer 5

Berücksichtigt diese Analyse nicht das Finden der Knotenoperation (obwohl es erforderlich ist) und nur die Einfügung selbst?

Sie haben es. Die Insertion an einem gegebenen Punkt geht davon aus, dass Sie bereits einen Zeiger auf das Element halten, die Sie einfügen möchten nach:

InsertItem(item * newItem, item * afterItem) 

Answer 6

Das Einsetzen selbst O (1) ist. Knoten finden ist O (n).

Answer 7

In diesem Artikel geht es darum, Arrays mit Listen zu vergleichen. Das Finden der Einfügeposition für Arrays und Listen ist O (N), so dass der Artikel sie ignoriert.

Answer 8

O (1) ist abhängig von dieser Tatsache, dass Sie einen Artikel haben, wo Sie den neuen Artikel einfügen werden. (vorher oder nachher). Wenn du es nicht tust, ist es O (n), weil du diesen Gegenstand finden musst.

Answer 9

Nein, es berücksichtigt nicht die Suche. Wenn Sie jedoch bereits einen Zeiger auf ein Element in der Mitte der Liste haben, wird an diesem Punkt O (1) eingefügt.

Wenn Sie suchen müssen, müssen Sie die Zeit für die Suche hinzufügen, die O (n) sein sollte.

Answer 10

Ich denke, es ist nur ein Fall von dem, was Sie für die O() Notation zählen. Im Falle des Einfügens der normalen Operation zum Zählen sind Kopiervorgänge. Bei einem Array wird beim Einfügen in der Mitte alles oberhalb des Speicherorts kopiert. Bei einer verknüpften Liste werden zwei Zeiger gesetzt. Sie müssen den Standort finden, egal was eingefügt wird.

Answer 11

Für den Vergleich mit einem Array, was das Diagramm zeigt, ist es O (1), weil Sie nicht alle Elemente nach dem neuen Knoten verschieben müssen.

Also ja, sie gehen davon aus, dass Sie bereits den Zeiger auf diesen Knoten haben, oder dass das Abrufen des Zeigers trivial ist. Mit anderen Worten, das Problem wird angegeben: "gegeben Knoten bei X, was ist der Code nach diesem Knoten einfügen?" Sie beginnen am Einfügepunkt.

Answer 12

Wenn Sie die Referenz des einzufügenden Knotens haben, nachdem die Operation O (1) für eine verkettete Liste ist.
Für ein Array ist es immer noch O (n), da Sie alle konsekutiven Knoten verschieben müssen.

Answer 13

Die häufigsten Fälle sind wahrscheinlich am Anfang oder am Ende der Liste einfügen (und die Enden der Liste kann keine Zeit zu finden).

Vergleichen Sie das mit dem Einfügen von Elementen am Anfang oder am Ende eines Arrays (die Größe des Arrays erfordert, wenn es am Ende ist, oder die Größe ändern und verschieben alle Elemente, wenn es am Anfang ist).

Answer 14

Die Einfügung in eine verkettete Liste unterscheidet sich von der Iteration.Sie finden den Gegenstand nicht, Sie setzen Zeiger zurück, um den Gegenstand dorthin zu setzen. Es spielt keine Rolle, ob es in der Nähe des vorderen Endes oder nahe dem Ende eingefügt wird, die Einfügung bezieht sich immer noch auf Zeiger, die neu zugewiesen werden. Es hängt natürlich davon ab, wie es implementiert wurde, aber das ist die Stärke von Listen - Sie können sie einfach einfügen. Der Zugriff über den Index ist der Ort, an dem ein Array leuchtet. Für eine Liste ist es normalerweise O (n), den n-ten Gegenstand zu finden. Zumindest erinnere ich mich an die Schule.