Perché l'inserimento è nel mezzo di un elenco collegato O (1)?

Question

Secondo l'articolo Wikipedia su elenchi collegati , inserendolo nel mezzo di un elenco collegato è considerato O (1). Penserei che sarebbe O (n). Non avresti bisogno di individuare il nodo che potrebbe essere vicino alla fine dell'elenco?

Questa analisi non tiene conto del rilevamento dell'operazione del nodo (sebbene sia necessaria) e solo dell'inserimento stesso?

MODIFICA :

  

Gli elenchi collegati presentano numerosi vantaggi rispetto agli array. L'inserimento di un elemento in un punto specifico di un elenco è un'operazione a tempo costante, mentre l'inserimento in un array può richiedere lo spostamento della metà degli elementi o più.

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

Array:

• Ricerca del punto di inserimento / eliminazione O (1)
• Esecuzione dell'inserimento / eliminazione O (n)

Elenchi collegati:

• Ricerca del punto di inserimento / cancellazione O (n)
• Esecuzione dell'inserimento / eliminazione O (1)

Penso che l'unica volta che non dovresti trovare la posizione è se hai tenuto una sorta di puntatore (come in alcuni casi con la testa e la coda). Quindi non possiamo dire con certezza che gli elenchi collegati battono sempre gli array per le opzioni di inserimento / eliminazione.

Answer 1

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

Answer 2

L'inserimento stesso è O (1). La ricerca del nodo è O (n).

Answer 3

No, quando decidi di voler inserire, si presume che tu sia già nel mezzo dell'iterazione dell'elenco.

Le operazioni sugli elenchi collegati vengono spesso eseguite in modo tale da non essere realmente trattate come un "elenco" generico, ma come una raccolta di nodi: pensa al nodo stesso come l'iteratore per il tuo ciclo principale. Quindi, mentre sfogli l'elenco, noti come parte della tua logica aziendale che è necessario aggiungere un nuovo nodo (o cancellarne uno vecchio) e lo fai. Puoi aggiungere 50 nodi in una singola iterazione e ciascuno di questi nodi è solo O (1) il momento di scollegare due nodi adiacenti e inserirne uno nuovo.

Modifica: amico, scrivi un secondo paragrafo e all'improvviso invece di essere il primo risponditore sei il 5 ° a dire la stessa cosa del primo 4!

Answer 4

Ai fini del confronto con un array, che è quello che mostra quel grafico, è O (1) perché non è necessario spostare tutti gli elementi dopo il nuovo nodo.

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

Answer 5

L'inserimento in un elenco collegato è diverso dall'iterazione attraverso esso. Non stai individuando l'elemento, stai reimpostando i puntatori per inserirlo. Non importa se verrà inserito vicino alla parte frontale o vicino alla fine, l'inserimento comporta comunque la riassegnazione dei puntatori. Dipende da come è stata implementata, ovviamente, ma questo è il punto di forza degli elenchi: puoi inserirlo facilmente. L'accesso tramite indice è dove un array brilla. Per un elenco, tuttavia, sarà in genere O (n) per trovare l'ennesimo elemento. Almeno questo è quello che ricordo da scuola.

Answer 6

Perché non comporta alcun loop.

L'inserimento è come:

• inserisci elemento
• link al precedente
• link al prossimo
• fatto

questo è il tempo costante in ogni caso.

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

Answer 7

  

Questa analisi non tiene conto del rilevamento dell'operazione del nodo (sebbene sia necessaria) e solo dell'inserimento stesso?

Hai capito. L'inserimento in un determinato punto presuppone che tu abbia già un puntatore sull'elemento che vuoi inserire dopo:

InsertItem(item * newItem, item * afterItem)

Answer 8

L'inserimento è O (1) quando sai dove lo inserirai.

Answer 9

No, non tiene conto della ricerca. Ma se hai già un puntatore a un elemento in mezzo all'elenco, l'inserimento in quel punto è O (1).

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

Answer 10

L'articolo tratta del confronto tra matrici e liste. Trovare la posizione di inserimento per entrambi gli array e gli elenchi è O (N), quindi l'articolo lo ignora.

Answer 11

O (1) dipende dal fatto che hai un oggetto in cui inserirai il nuovo oggetto. (prima o dopo). Se non & # 180; t, è O (n) perché devi trovare quell'elemento.

Answer 12

Penso che sia solo un caso di ciò che scegli di contare per la notazione O (). Nel caso di inserimento delle normali operazioni da contare sono le operazioni di copia. Con un array, l'inserimento nel mezzo implica la copia di tutto al di sopra della posizione in memoria. Con un elenco collegato, questo diventa l'impostazione di due puntatori. Devi trovare la posizione, non importa cosa inserire.

Answer 13

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

Answer 14

I casi più comuni si stanno probabilmente inserendo all'inizio o alla fine dell'elenco (e le estremità dell'elenco potrebbero non impiegare tempo per trovare).

Contrastalo 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).