In che modo LinkedList aggiunge (int, E) di complessità O (1)?

Question

Dal linked-list tag wiki estratto:

Una lista concatenata è una struttura dati in cui gli elementi contengono riferimenti alla (e facoltativamente il precedente) all'elemento successivo. Collegati elenchi offrono O (1) inserire e rimozione in qualsiasi posizione, O (1) Lista concatenazione, e O (1) l'accesso alla parte anteriore (e facoltativamente schienale) posizioni e O (1) all'elemento successivo accesso. L'accesso casuale ha la complessità O (N) e di solito non è implementato.

^{(sottolineatura mia)}

Sono rimasto sorpreso di leggere questo – come può l'elenco inserire ad un indice caso con una complessità inferiore a quello semplicemente lettura tale indice?

Così ho visto the source code for java.util.LinkedList. Il add(int, E) method è:

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

Il addBefore(E, Entry<E> method è semplicemente puntatore riassegnazione, ma c'è anche la 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; 
} 

Anche con l'ottimizzazione half-size, il ciclo for qui (uno o l'altro) mi sembra un dono morto che questo metodo (e quindi add(int, E)) opera in uno scenario minimo nel caso peggiore di tempo O (n), e certamente non costante.

Cosa mi manca? Sto fraintendendo la notazione O grande?

Answer 1

Bene, supportano gli inserimenti a tempo costante in posizioni arbitrarie - ma solo se si ha un puntatore alla voce dell'elenco dopo la quale o davanti a cui si desidera inserire qualcosa. Ovviamente, questo non funzionerà se si ha solo l'indice, ma non è quello che si fa di solito nel codice ottimizzato.

In Java, è possibile anche farlo, ma only using a list iterator.

Questa proprietà di elenchi collegati è il loro più grande vantaggio rispetto agli arraylisti o così - per esempio, se si desidera rimuovere un utente dall'elenco utenti di una chatroom, è possibile memorizzare un puntatore alla posizione dell'utente nella lista utenti in l'utente in modo che, quando vuole uscire dalla stanza, possa essere implementato come operazione O(1).

Answer 2

Questo perché l'articolo che stai leggendo considera "arrivare a quell'indice" come operazione separata. L'articolo presuppone che tu sia già nell'indice che desideri eseguire add (int, E).

Per concludere:

inserire o rimuovere funzionamento = O (1)

Trovare nodo n ^th index = O (n)

Answer 3

Il funzionamento linking il nuovo nodo su qualsiasi nodo è O (1) ma l'operazione di che trova (aiuta al ciclo) l'indice interessato è def inizialmente O (n).

Non c'è magia;)

Answer 4

La pagina wiki si cita dice:

O (1) Inserire e rimozione in qualsiasi posizione

Allora vi chiedo:

Sono stato sorpreso di leggere questo - come può la lista rt in un caso indice

Qui sta la confusione: i termini posizione e indice non vengono utilizzati per indicare la stessa cosa. Il wiki parla di un iteratore o di un puntatore, non di un indice.