Warum ist in der Mitte eines verknüpften Liste O Einfügen (1)?

StackOverflow https://stackoverflow.com/questions/840648

  •  20-08-2019
  •  | 
  •  

Frage

Nach dem Wikipedia-Artikel über verkettete Listen , Einfügen in der Mitte eine verkettete Liste wird als O (1). Ich würde denken, es wäre O (n). Würden Sie nicht brauchen, um den Knoten zu finden, das in der Nähe des Endes der Liste sein könnte?

Ist diese Analyse nicht Rechnung für die Feststellung des Knotens Betriebes (auch wenn es erforderlich ist) und nur das Einsetzen selbst?

Bearbeiten :

  

Verknüpfte Listen haben mehrere Vorteile gegenüber Arrays. Einsetzen eines Element an einer bestimmten Stelle einer Liste ist ein konstanter Zeitbetrieb, während der Insertion in einem Array erfordert Hälfte der Elemente zu bewegen, oder mehr.

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

Arrays:

  • Finden des Punktes der Insertion / Deletion O (1)
  • Durchführung der Insertion / Deletion O (n)

Verknüpfte Listen:

  • Finden des Punktes der Insertion / Deletion O (n)
  • Durchführung der Insertion / Deletion O (1)

Ich denke, das einzige Mal, wenn Sie würde die Position nicht gefunden haben, ist, wenn Sie irgendeine Art von Zeiger darauf gehalten (wie mit dem Kopf und der Schwanz in einigen Fällen). So können wir nicht rundweg sagen, dass verkettete Listen immer Arrays schlagen für Einfügen / Löschen-Optionen.

War es hilfreich?

Lösung

Sie sind richtig, der Artikel „Indexing“ als separater Betrieb hält. So Einsetzen selbst O (1), aber in diesem mittleren Knoten bekommen ist O (n).

Andere Tipps

Die Insertion selbst ist O (1). Knoten Befund ist O (n).

Nein, wenn Sie entscheiden, dass Sie einfügen möchten, wird es angenommen, Sie sind bereits in der Mitte durch die Liste der laufen.

Operationen auf verlinkte Listen werden oft in der Weise, dass sie nicht wirklich als eine generische „Liste“ behandelt werden, sondern als eine Sammlung von Knoten - man denke an den Knoten selbst als Iterator für Ihre Hauptschleife. So wie Sie durch die Liste sind Stossen Sie feststellen, als Teil Ihrer Geschäftslogik, die ein neuer Knoten hinzugefügt werden muss (oder eine alte gelöscht), und Sie tun so. Sie können 50 Knoten in einer einzigen Iteration hinzufügen und jeder dieser Knoten ist nur O (1) die Zeit zwei benachbarten Knoten zu entkoppeln und Ihre neuen ein ..

Edit: Man, geben Sie einen zweiten Absatz und ganz plötzlich statt der Ersthelfer des Seins bist du der 5. sagen das gleiche wie das erste 4

Für die Zwecke der mit einer Reihe zu vergleichen, das ist, was das Diagramm zeigt, ist es O (1), weil Sie nicht alle Elemente nach dem neuen Knoten zu verschieben.

Also ja, sie gehen davon aus, dass Sie bereits die Zeiger auf diesen Knoten haben, oder dass der Zeiger immer trivial. Mit anderen Worten, das Problem ist, erklärt: „ gegebenen Knoten bei X , was der Code nach diesem Knoten einfügen?“ Sie erhalten am Insertpunkt zu starten.

Einfügen in eine verknüpfte Liste ist anders als über sie iterieren. Sie sind das Produkt nicht lokalisieren, Sie Zeiger Zurücksetzen dort den Punkt zu bringen. Dabei spielt es keine Rolle, ob es in der Nähe des vorderen Ende oder nahe dem Ende eingefügt werden soll, noch die Einfügung beinhaltet Zeiger neu zugewiesen werden. Es wird davon abhängen, wie es durchgeführt wurde, natürlich, aber das ist die Stärke von Listen - Sie können leicht eingefügt werden. Zugriff über Index ist, wo ein Array glänzt. Eine Liste, wird es jedoch typischerweise O (n) sein, das n-te Element zu finden. Zumindest ist das, was ich aus der Schule erinnern.

Weil es kein looping beinhaltet.

Einfügen ist wie:

  • Einsatzelement
  • Link zur vorherigen
  • Link zum nächsten
  • fertig

Das ist die Konstante Zeit auf jeden Fall.

Folglich Einsetzen n Elemente eines nach dem anderen ist O (n).

  

Ist diese Analyse nicht Rechnung für die Feststellung des Knotens Betriebes (auch wenn es erforderlich ist) und nur das Einsetzen selbst?

Du hast es. Die Insertion an einem gegebenen Punkt geht davon aus, dass Sie bereits einen Zeiger auf das Element halten, das Sie einfügen wollen nach: 

InsertItem(item * newItem, item * afterItem)

Einfügen ist O (1), wenn Sie wissen, wohin du gehst, es zu setzen.

Nein, es berücksichtigt nicht für die Suche. Aber wenn Sie bereits haben halten einen Zeiger auf ein Element in der Mitte der Liste, an diesem Punkt eingefügt ist O (1).

Wenn Sie es suchen haben, dann würden Sie auf die Zeit für die Suche hinzufügen müssen, die O sein sollte (n).

Der Artikel ist über Arrays mit Listen zu vergleichen. Das Finden der Insert-Position für beide Arrays und Listen ist O (N), so der Artikel ignoriert es.

O (1) in Abhängigkeit von dieser Tatsache, dass Sie einen Artikel, in dem Sie das neue Element eingefügt werden. (vorher oder nachher). Falls Sie nicht, es ist O (n) weil Sie diesen Artikel finden müssen.

Ich denke, es ist nur ein Fall von dem, was Sie wählen, für die O () Notation zählen. Im Falle der Verwendung des normalen Betriebs Einfügen ist Operationen Kopie zu zählen. Mit einer Reihe, in der Mitte des Einfügen beinhaltet alles oberhalb der Stelle oben im Speicher zu kopieren. Mit einer verknüpften Liste, wird diese zwei Zeiger zu setzen. Sie müssen die Lage egal finden, was einzufügen.

Wenn Sie die Referenz des Knotens eingefügt werden, nachdem die Operation O (1) für eine verkettete Liste.
Für ein Array ist es immer noch O (n), da Sie alle consequtive Knoten zu bewegen haben.

Die häufigsten Fälle sind wahrscheinlich am Anfang oder am Ende der Liste eingefügt (und die Enden der Liste möglicherweise keine Zeit in Anspruch nehmen zu finden).

Kontrast, der mit Gegenständen am Anfang oder am Ende eines Arrays eingefügt (der das Array Ändern der Größe erfordert, wenn es am Ende der oder Skalieren und Bewegen aller Elemente, wenn sie am Anfang ist).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top