Wie ist LinkedList add (int, E) O (1) Komplexität?

Question

Vom linked-list tag wiki Auszug:

Eine verkettete Liste ist eine Datenstruktur, in der die Elemente Verweise auf das nächste (und gegebenenfalls das vorherige) Element enthalten. Verknüpfte Listen bieten O (1) Einfügen und Entfernen an jeder Position, O (1) Liste Verkettung und O (1) Zugriff auf die vorderen (und optional zurück) Positionen sowie O (1) nächstes Element Zugriff. Random Access hat O (N) Komplexität und ist in der Regel nicht implementiert.

^{(Hervorhebung von mir)}

Ich war überrascht, das lesen – wie kann die Liste bei einem zufälligen Index mit einer geringeren Komplexität einsetzt als nur zu lesen, dass Index?

So schaute ich auf the source code for java.util.LinkedList. Die add(int, E) method ist:

public void add(int index, E element) { 
    addBefore(element, (index==size ? header : entry(index))); 
} 

Die addBefore(E, Entry<E> method ist einfach Neuzuordnung Zeiger, aber es gibt auch die entry(int) method:

if (index < 0 || index >= size) 
     throw new IndexOutOfBoundsException("Index: "+index+ 
              ", Size: "+size); 
    Entry<E> e = header; 
    if (index < (size >> 1)) { 
     for (int i = 0; i <= index; i++) 
      e = e.next; 
    } else { 
     for (int i = size; i > index; i--) 
      e = e.previous; 
    } 
    return e; 
} 

Auch bei der Halbgrößenoptimierung, die for Schleife in hier (die eine oder andere) ein untrügliches Zeichen scheint mir, dass diese Methode (und damit add(int, E)) in einem Worst-case-Szenario von O (n) Zeit, und schon gar nicht konstante Zeit Minimum arbeitet.

Was fehlt mir? Verkenne ich die Groß-O-Notation?

Answer 1

Nun, sie unterstützen konstante Zeit Inserts an beliebigen Positionen - aber nur wenn Sie haben einen Zeiger auf den Listeneintrag, nach dem oder vor dem Sie etwas einfügen möchten. Natürlich funktioniert das nicht, wenn Sie nur den Index haben, aber das ist nicht das, was Sie normalerweise in optimiertem Code tun.

In Java können Sie das auch tun, aber only using a list iterator.

Diese Eigenschaft der verknüpften Listen ist ihr größter Vorteil im Vergleich zu Arraylisten oder so - wenn Sie beispielsweise einen Benutzer aus der Benutzerliste eines Chatrooms entfernen möchten, können Sie in der Benutzerliste einen Zeiger auf die Position des Benutzers speichern der Benutzer, so dass, wenn er will, den Raum verlassen, die als O(1) Betrieb implementiert werden kann. Diese

Answer 2

ist, weil der Artikel, die Sie in Betracht gezogen werden, das Lesen als separate Operation „zu diesem Index bekommen“. Der Artikel geht davon aus, dass Sie sich bereits in dem Index befinden, den Sie hinzufügen möchten (int, E).

Zum Schluss:

Insert oder Bedienung entfernen = O (1)

Knoten an n Finding ^th index = O (n)

Answer 3

Der Betrieb von Verknüpfungs der neue Knoten zu jedem Knoten ist O (1), aber die Operation Suche (hilft der Schleife) der betroffene Index ist def endlich O (n).

Es gibt keine Magie ist;)

Answer 4

Die Wiki-Seite, die Sie zitieren, sagt:

O (1) einsetzen und die Entfernung auf jeder Position

Dann fragen Sie:

Ich war überrascht, dies zu lesen - wie kann die Liste rt zu einem zufälligen Index

Hierin liegt die Verwirrung: die Begriffe Position und Index nicht verwendet werden, das Gleiche bedeuten. Das Wiki spricht von einem Iterator oder einem Zeiger, nicht von einem Index.