Algoritmo per l'eliminazione di un elemento in una sola lista collegata con O (1) la complessità

Question

Sono uno studente di informatica in Germania. Il mio professore ha dato utilizzare la seguente domanda a cui pensare:

'Dato un riferimento ad un nodo in una sola lista collegata (che non è l'ultimo nodo). Dare un algoritmo per eliminare questo elemento dalla lista che ha complessità O (1) pur mantenendo l'integrità '.

ho pensato a questo, ma sono abbastanza sicuro, che non v'è tale algoritmo. poiché si tratta di un singolo elenco collegato, è necessario eseguire il ciclo di ogni nodo nell'elenco fino a raggiungere il nodo che deve essere eliminato, poiché è necessario modificare il puntatore successivo nel nodo prima dell'eliminazione. Quale porterebbe a O (n) complessità.

Mi sto perdendo qualcosa?

Answer 1

Dipende se i nodi sono mutabili (valore).

Ci è un modo di fare che, se si può fare quello che vuoi con i nodi:

toDelete.value = toDelete.next.value 
toDelete.next = toDelete.next.next 

Tutte le informazioni dal toDelete è ora stato sovrascritto, dalle informazioni nella vecchia toDelete.next. (A seconda della piattaforma, potrebbe essere necessario liberare il vecchio toDelete.next - il che significa mantenere un riferimento temporaneo ad esso. Non va bene se qualcun altro ha ancora un riferimento ad esso, ovviamente. In Java/C# lo ignoreresti .)

ho cercato di trovare un modo di accennare a esso senza darlo via, ma è un po 'complicato ...

essa si basa su questo non essere l'ultimo nodo della lista però.

Answer 2

Non esattamente considerato l'eliminazione di un nodo, ma è possibile copiare i dati del nodo successivo alla corrente ed eliminare il nodo successivo:

// pseudocode: 
this.data = next.data; 
var temp = this.next; 
this.next = next.next; 
delete temp; 

Answer 3

Sì. Si mantiene come puntatore iteratore, un puntatore al puntatore successivo dell'elenco precedente.

walk = &head; 
while (!match(*walk)) { 
    walk = &walk[0]->next; 
    if (!*walk) return ; 
} 
*walk = walk[0]->next; 

Answer 4

Se i nodi sono strutture di base in memoria, è possibile copiare il contenuto del nodo "successivo" nella locazione di memoria del nodo cancellato, e deallocare la memoria in cui il nodo "next" di una volta.

Answer 5

si Supponendo che avete il puntatore al nodo che si desidera eliminare. Replica il valore successivo nel nodo corrente. Sostituisci il puntatore corrente sul nodo il prossimo a cui si fa riferimento.

Answer 6

spostare i dati, non il collegamento. guarda a questo altro thread: Deleting a middle node from a single linked list when pointer to the previous node is not available