Perché si sta eliminando una singola lista collegata O (1)?

Question

Non capisco perché l'eliminazione alla fine di una singola lista collegata vada in O (1) volta, come dice il wikipedia article.

Un singolo elenco collegato è costituito da nodi. Un nodo contiene un tipo di dati e un riferimento al nodo successivo. Il riferimento dell'ultimo nodo nell'elenco collegato è nullo.

-------------- --------------   -------------- 
| data | ref | -> | data | ref | -> ... -> | data | ref | 
-------------- --------------   -------------- 

Posso effettivamente rimuovere l'ultimo nodo in O (1). Ma in tal caso non si imposta il riferimento del nuovo ultimo nodo, quello precedente, a null poiché contiene ancora il riferimento all'ultimo nodo eliminato. Quindi mi chiedevo se lo trascurassero nell'analisi del tempo di esecuzione? O è consueto che tu non debba cambiarlo dal momento che il riferimento, beh, non punta a nulla, e tale è visto come nulla?

Perché se non fosse trascurato, direi che l'eliminazione è O (n). Dal momento che devi scorrere l'intera lista per arrivare al nuovo nodo e impostare il suo riferimento anche su null. Solo in una doppia lista collegata sarebbe davvero O (1).

-edit- Forse questo punto di vista dà un po 'più di chiarezza. Ma vedo "cancellazione di un nodo" cancellando con successo il nodo stesso e impostando il riferimento precedente su null.

Answer 1

Non sono sicuro di vedere nell'articolo di Wikipedia dove si dice che è possibile rimuovere l'ultima voce di un elenco collegato singolarmente in O (1) tempo, ma questa informazione non è corretta nella maggior parte dei casi. Dato qualsiasi singolo nodo in un elenco collegato, è sempre possibile rimuovere il nodo dopo di esso in tempo O (1) ricablando l'elenco attorno a quel nuovo nodo. Di conseguenza, se ti venisse assegnato un puntatore al penultimo nodo in un elenco collegato, potresti eliminare l'ultimo elemento dell'elenco in O (1).

Tuttavia, se nella lista non sono presenti puntatori aggiuntivi diversi da un puntatore testa, non è possibile eliminare l'ultimo elemento dell'elenco senza eseguire la scansione fino alla fine dell'elenco, il che richiederebbe Θ (n) tempo, come hai notato. Sei assolutamente corretto che eliminare l'ultimo nodo senza prima cambiarne i puntatori sarebbe un'Idea Pessima, poiché se lo facessi, l'elenco esistente conterrebbe un puntatore a un oggetto deallocato.

Più in generale - il costo per eseguire un inserimento o una cancellazione in un elenco collegato singolarmente è O (1), assumendo che si abbia un puntatore al nodo subito prima di quello che si desidera inserire o eliminare. Tuttavia, potrebbe essere necessario eseguire un lavoro extra (fino a Θ (n)) per trovare quel nodo.

Spero che questo aiuti!

Answer 2

L'aggiunta/soppressione QUALSIASI nodo QUALSIASI posizione è O (1). Il codice gioca solo con costi fissi (pochi calcoli di puntatori e malloc/liberi) per aggiungere/eliminare il nodo. Questo costo aritmetico è fisso per ogni caso specifico.

Tuttavia, il costo per raggiungere (indicizzazione) il nodo desiderato è O (n).

L'articolo si limita a elencare l'aggiunta/eliminazione in più sottocategorie (aggiungendo in mezzo, inizio, fine) per mostrare che il costo per l'aggiunta nel mezzo è diverso dall'aggiunta all'inizio/fine (ma i rispettivi costi sono ancora fissi).

Answer 3

Ad esempio, è possibile avere un puntatore all'ultimo elemento ("secondo dalla fine") e quando si elimina: 1. Elimina * accanto a questo elemento "secondo dalla fine". 2. Imposta questo "secondo dalla fine" * accanto a NULL

Answer 4

O (1) significa semplicemente "costo costante". Non significa 1 operazione. Significa "al massimo C" operazioni con C fisse indipendentemente dagli altri parametri che cambiano (come la dimensione dell'elenco). Infatti, nel mondo a volte confuso di big-Oh: O (1) == O (22).

Al contrario l'eliminazione dell'intero elenco ha un costo O (n), poiché il costo cambia con la dimensione (n) dell'elenco.

Answer 5

Se si include il costo di riparazione del nodo pendente, è comunque possibile farlo in O (1) con l'uso del nodo sentinella per la fine (descritto anche in quella pagina).

L'elenco "vuoto" inizia con un singolo sentinella

Head -> [Sentinel] 

Aggiungere un po 'di roba

Head -> 1 -> 2 -> 3 -> [Sentinel] 

Ora eliminare la coda (3) contrassegnando il nodo che era 3 come non valido, e quindi rimuovere il link al vecchio sentinella, e liberare la memoria per esso:

Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] 

Answer 6

per riferimento futuro, devo dire dopo alcune ricerche ho scoperto che nessuno degli argomenti forniti in risposta a questa domanda è pertinente. La risposta è che decidiamo semplicemente che la cima della pila sia la testa dell'elenco collegato (piuttosto che la coda). Ciò introdurrà un leggero cambiamento nella routine di push, ma poi il pop e il push rimarranno entrambi o (1).