inserimento lista concatenata tempo di esecuzione confusione

Question

ho cercato di confermare il tempo di esecuzione per l'inserimento in lista concatenata e sembra che ci sono due risposte diverse.

Per inserire un elemento alla fine di un elenco collegato, penserei che occorrerebbe O (n) dal momento che deve passare alla fine dell'elenco per accedere alla coda. Ma alcune delle risposte che ho visto dice O (1)? Stanno assumendo che tutte le implementazioni di liste collegate di un puntatore alla coda? Se è così, è un'ipotesi accettabile?

In secondo luogo, alcuni luoghi suggeriscono anche che l'inserimento di un elemento nel mezzo di una lista concatenata è O (1) di cui sono confuso a causa dello stesso ragionamento della traversa verso il centro della lista per inserirlo.

Qualcuno potrebbe chiarire? Grazie.

Answer 1

Inserimento di una lista collegata è O (1) se si dispone di un puntatore al nodo in cui si desidera inserire l'elemento. Trovare questo nodo può essere O (n) a seconda di cosa si vuole fare.

Se si mantiene un puntatore alla coda della lista, allora non c'è bisogno di guardare per esso e poi l'inserimento è O (1).

E no, non tutte le implementazioni lista collegate hanno un puntatore alla fine della lista.

Esempio

Si supponga di avere una lista vuota a cui si aggiunge un singolo nodo, x. Quindi aggiungi i nodi n all'elenco prima e dopo x. È ancora possibile inserire un singolo nodo dopo x semplicemente aggiornando il puntatore next (e il nuovo nodo), indipendentemente dal numero di nodi presenti nell'elenco.

Answer 2

Modifiche elenco collegato implicano due operazioni:

1. localizzare il nodo per aggiungere il nuovo nodo di
2. effettivamente aggiungendo il nodo, cambiando i puntatori nodo

In lista concatenata, la seconda operazione è un'operazione O(1), quindi si tratta del costo delle prime operazioni.

Quando aggiungendo all'ultimo nodo, implementazioni naif lista collegata comporterebbe O(n) iterazione tempo. Tuttavia, le buone librerie di elenchi collegati rappresentano gli usi più comuni e casi speciali che accedono all'ultimo nodo. Questa ottimizzazione si tradurrebbe in recupero O(1) dell'ultimo elemento, con conseguente tempo di inserimento complessivo O(1) alla fine.

Per quanto riguarda il mezzo, la tua analisi è corretta in quanto localizzare il nodo sarebbe anche prendere O(n). Tuttavia, alcune librerie espongono un metodo che utilizza un puntatore a cui deve essere inserito il nuovo nodo anziché l'indice (ad esempio C++list). Questo elimina il costo lineare, risultando in tutto O(1).

Mentre l'inserimento al centro è solitamente pensato come operazione O(n), può essere ottimizzato in O(1) in alcuni casi.Questo è l'opposto della lista di matrice, in cui l'operazione di inserimento stessa (la seconda operazione) è O(n), poiché tutti gli elementi in posizioni più alte devono essere riposizionati. Questa operazione non può essere ottimizzata.

Per l'inserimento Un'implementazione ingenua di un elenco collegato comporterebbe il tempo di inserimento O(n). Tuttavia, i buoni scrittori di librerie di elenchi collegati ottimizzerebbero per i casi comuni, in modo da mantenere un riferimento agli ultimi elementi (o avere un'implementazione di elenchi concatenati circolari), risultando in un tempo di inserimento O(1).

Come per l'inserimento al centro. Alcune librerie come quella di C++ hanno una posizione suggerita per l'inserimento. Prenderanno un puntatore al nodo della lista, dove sarà aggiunto il nuovo. Tali inserzioni costerebbero O(1). Non penso che tu possa raggiungere O(1) per numero di indice.

Questo è assegnato a un elenco di array, in cui l'inserimento al centro richiede il riordino di tutti gli elementi più alti di esso, quindi deve essere un'operazione O(n).

Answer 3

Per the Java LinkedList source code, Java raggiunge lo O (1) per LinkedList operazioni coda dando al header Entry un collegamento all'elemento coda via header.previous. Quindi se vuoi l'ultimo elemento, la classe può sempre restituire header.previous, tenendo conto del tempo costante.

Suppongo che molte altre lingue utilizzino la stessa strategia di base.

Answer 4

Ovviamente probabilmente hai guardato la voce di wikipedia http://en.wikipedia.org/wiki/Linked_list. Vedo la tabella in cui stanno specificando che sia l'inserimento/eliminazione dalla fine e nel mezzo della lista hanno prestazioni O (1), ma non riescono a elaborare su come hanno determinato che.

Ci sono alcune risposte interessanti a una domanda simile qui su StackOverflow a Why is inserting in the middle of a linked list O(1)?. Il poster originale di quella domanda ha edificato il suo post e ha fatto un punto in cui crede che quando si dice che l'inserimento/cancellazione sia O (1) stanno parlando dell'operazione di inserimento vera e propria e non del ritrovamento di dove inserire. Questo ha senso, ma non ho visto quello formalmente dichiarato in nessuno degli articoli che ho trovato a questo punto.

Answer 5

Se non si mutano i nodi del proprio elenco (semplicemente) collegato, è necessario O (n) tempo per inserire in una posizione arbitraria nell'elenco (poiché è necessario copiare tutti i nodi dall'inizio del elenca la posizione del nuovo elemento: è O (1) per un elenco mutabile se hai già un puntatore al nodo in cui desideri inserire un elemento e O (n) se devi cercarlo. In entrambi i casi, è necessario solo O (1) tempo per inserire un elemento all'inizio dell'elenco.Se spesso è necessario inserire un elemento nel mezzo dell'elenco (caso O (n)), è necessario utilizzare un altro dato

Answer 6

Penso che una ragione della tua confusione sia il fatto che stai pensando come se ci fosse un elenco link ideale/canonico, che ha o fa non ha determinati puntatori testa/coda. La realtà è che qualsiasi struttura di dati lineare (cioè senza ramificazioni) che accede agli elementi passando per i puntatori dagli elementi precedenti è fondamentalmente una lista collegata. Indipendentemente dal fatto che tu continui a puntare al primo, all'ultimo, al k-esimo elemento, dipende interamente da te. Quindi, se hai bisogno di una lista in cui hai spesso bisogno di inserire/eliminare elementi in decima posizione, puoi semplicemente implementarne una che abbia un puntatore aggiuntivo al 9 ° elemento e farlo in O (1).

Un'altra cosa è che durante l'iterazione degli elementi di una lista concatenata, è possibile inserire un nuovo elemento subito dopo l'elemento corrente (e poco prima se è una lista doppia collegata) in O (1), perché hai già un puntatore.

Answer 7

Come sottolinea @Kaleb Brasee, l'inserimento in coda in Java è O (1) perché Java utilizza un elenco doppiamente collegato come implementazione LinkedList. Penso che questa sia una scelta abbastanza comune per molte implementazioni di SDK. Ad esempio, l'implementazione STL list è doppiamente collegata (source).