Perché si sta inserendo nel mezzo di una lista collegata O (1)?

Question

Secondo lo Wikipedia article on linked lists, l'inserimento nel mezzo di un elenco collegato è considerato O (1). Penserei che sarebbe O (n). Non avresti bisogno di localizzare il nodo che potrebbe essere vicino alla fine della lista?

Questa analisi non considera il rilevamento dell'operazione del nodo (sebbene sia richiesto) e solo l'inserimento stesso?

EDIT:

Le liste concatenate hanno diversi vantaggi rispetto array. L'inserimento di un elemento in un punto specifico di una lista è un'operazione a tempo costante, mentre l'inserimento in una matrice può richiedere il trasferimento di metà degli elementi o più.

L'affermazione di cui sopra è un po 'fuorviante per me. Correggetemi se sbaglio, ma credo che la conclusione dovrebbe essere:

Array:

• Trovare il punto di inserzione/delezione O (1)
• Esecuzione della inserzione/delezione O (n)

liste collegate:

• Trovare il punto di inserzione/delezione O (n)
• Esecuzione della inserzione/delezione O (1)

penso che l'unica volta che non avrebbe dovuto trovare la posizione è che se hai tenuto qualche una sorta di puntatore ad esso (come con la testa e la coda in alcuni casi). Quindi non possiamo dire chiaramente che le liste collegate battono sempre gli array per le opzioni di inserimento/cancellazione.

Answer 1

Si è corretto, l'articolo considera "Indicizzazione" come operazione separata. Quindi l'inserimento è esso stesso O (1), ma arrivare a quel nodo centrale è O (n).

Answer 2

Perché non comporta alcun loop.

Inserimento è come:

• elemento inserto
• link alla precedente
• link alla prossima
• fatto

questo è costante di tempo in ogni caso.

Di conseguenza, l'inserimento di n elementi uno dopo l'altro è O (n).

Answer 3

L'inserimento è O (1) una volta che sai dove lo metti.

Answer 4

No, quando decidi di voler inserire, si presume che tu stia già nel mezzo di scorrere l'elenco.

Le operazioni sugli elenchi collegati vengono spesso eseguite in modo tale da non essere trattate come una "lista" generica, ma come una raccolta di nodi: si pensi al nodo stesso come iteratore del ciclo principale. Quindi, mentre stai sfogliando l'elenco, noti come parte della tua logica aziendale che un nuovo nodo deve essere aggiunto (o uno vecchio eliminato) e lo fai. È possibile aggiungere 50 nodi in un'unica iterazione.

Modifica: Man, digiti un secondo paragrafo e all'improvviso invece di essere il primo interlocutore sei il quinto dicendo la stessa cosa dei primi 4!

Answer 5

Questa analisi non considera il rilevamento dell'operazione del nodo (sebbene sia necessario) e solo l'inserimento stesso?

Hai capito. Inserimento in un determinato punto presuppone che già in possesso di un puntatore alla voce che si desidera inserire dopo:

InsertItem(item * newItem, item * afterItem) 

Answer 6

L'inserimento in sé è O (1). Il rilevamento dei nodi è O (n).

Answer 7

L'articolo riguarda il confronto di array con elenchi. Trovare la posizione dell'inserto per entrambi gli array e gli elenchi è O (N), quindi l'articolo lo ignora.

Answer 8

O (1) dipende dal fatto che si dispone di un articolo in cui inserire il nuovo elemento. (prima o dopo). Se non lo fai, è O (n) perché devi trovare quell'oggetto.

Answer 9

No, non tiene conto della ricerca. Ma se hai già un puntatore a un oggetto nel mezzo della lista, inserendo in quel punto è O (1).

Se devi cercarlo, devi aggiungere il tempo per la ricerca, che dovrebbe essere O (n).

Answer 10

Penso che sia solo il caso di ciò che si sceglie di contare per la notazione O(). Nel caso di inserimento della normale operazione da contare sono le operazioni di copia. Con un array, l'inserimento nel mezzo comporta la copia di tutto ciò che si trova sopra la posizione in memoria. Con un elenco collegato, questo diventa impostato su due indicatori. Devi trovare la posizione, non importa cosa inserire.

Answer 11

Per scopi di confronto con un array, che è quello che mostra il grafico, è O (1) perché non è necessario spostare tutti gli elementi dopo il nuovo nodo.

Quindi sì, presuppongono che tu abbia già il puntatore a quel nodo, o che ottenere il puntatore sia banale. In altre parole, viene indicato il problema: "dato nodo su X, qual è il codice da inserire dopo questo nodo?" Puoi iniziare dal punto di inserimento.

Answer 12

Se si dispone del riferimento del nodo da inserire dopo l'operazione è O (1) per un elenco collegato.
Per un array è ancora O (n) poiché è necessario spostare tutti i nodi consequtive.

Answer 13

I casi più comuni sono probabilmente l'inserimento all'inizio o alla fine dell'elenco (e le estremità dell'elenco potrebbero non richiedere tempo per trovare).

Contrasto che con l'inserimento di elementi all'inizio o alla fine di un array (che richiede il ridimensionamento dell'array se è alla fine, o il ridimensionamento e lo spostamento di tutti gli elementi se è all'inizio).

Answer 14

L'inserimento in un elenco collegato è diverso dall'iterazione su di esso.Non stai localizzando l'oggetto, stai reimpostando i puntatori per inserire l'elemento. Non importa se verrà inserito vicino al front-end o vicino alla fine, l'inserimento implica ancora che i puntatori vengano riassegnati. Dipenderà da come è stato implementato, ovviamente, ma questa è la forza delle liste - puoi inserirle facilmente. L'accesso tramite indice è dove risplende un array. Per un elenco, tuttavia, sarà in genere O (n) per trovare l'ennesimo elemento. Almeno questo è quello che ricordo da scuola.