Perché la complessità temporale dell'eliminazione dei nodi in elenchi con collegamenti concatenati (O (1)) più rapida dell'eliminazione dei nodi in elenchi concatenati (O (n))?Complessità temporale dell'eliminazione dei nodi negli elenchi con collegamento singolo e doppio
Ha a che fare con la complessità di correggere il puntatore successivo nel nodo precedente a quello che si sta eliminando.
Perché non si può guardare indietro ...
Il problema assume che il nodo da cancellare è noto e un puntatore a quel nodo è disponibile.
Per eliminare un nodo e collegare insieme il nodo precedente e quello successivo, è necessario conoscere i rispettivi indicatori. In una lista doppiamente collegata, entrambi i puntatori sono disponibili nel nodo che deve essere cancellato. La complessità temporale è costante in questo caso, cioè O (1).
Mentre in un elenco a collegamento singolo, il puntatore al nodo precedente è sconosciuto e può essere trovato solo attraversando l'elenco dalla testa fino a raggiungere il nodo che ha un puntatore del nodo successivo al nodo che deve essere eliminato . La complessità temporale in questo caso è O (n).
Nei casi in cui il nodo da eliminare è noto solo per valore, l'elenco deve essere ricercato e la complessità temporale diventa O (n) in entrambe le liste con collegamento singolo e doppio.
Questo non è corretto per quanto riguarda la rimozione di un nodo da un elenco collegato singolarmente che richiede complessità O (n) - vedere la mia risposta di seguito. C'è un trucco in cui si copia il valore dal nodo successivo da quello che viene rimosso e poi si salta quello in modo che punti al nodo in seguito, eliminando così la necessità di attraversare la lista. – Ben
L'inserimento e la cancellazione in una posizione nota è O (1). Tuttavia, trovare quella posizione è O (n), a meno che non sia la testa o la coda della lista.
Quando parliamo di complessità di inserimento e cancellazione, generalmente pensiamo che sappiamo già dove ciò accadrà.
A meno che l'elemento da eliminare sia il nodo principale (o primo), è necessario attraversare il nodo prima di quello da eliminare. Quindi, nel peggiore dei casi, cioè, quando abbiamo bisogno di cancellare l'ultimo nodo, il puntatore deve andare fino all'ultimo secondo nodo attraversando così (n-1) le posizioni, il che ci dà una complessità temporale di O (n) .
In realtà la cancellazione in elenchi concatenati può essere implementata anche in O (1).
Dato un elenco singolarmente concatenata con il seguente stato:
SinglyLinkedList:
Node 1 -> Node 2
Node 2 -> Node 3
Node 3 -> None
Head = Node 3
Siamo in grado di implementare delete Note 2 in modo tale:
Node 2 Value <- Node 3 Value
Node 2 -> None
Qui Sostituire il valore della Node 2 con il valore della sua prossima nodo (Node 3) e impostare il puntatore del valore successivo sul puntatore del valore successivo di Node 3 (None), ignorando l'efficace "duplicato" Node 3. Quindi nessuna traversata necessaria.
Compiti? Scrivi il codice per eliminare un nodo da un elenco collegato singolarmente, e quindi sarà ovvio. –
Penso che non ci dovrebbero essere abbreviazioni come dll nel titolo, ma non riesco a pensare ad una migliore. –