Come eliminare un nodo in un elenco di collegamenti singoli con un solo puntatore che punta al nodo da eliminare?Eliminare un nodo nell'elenco di link singoli
[di inizio e fine puntatori non sono noti, le informazioni disponibili sono puntatore al nodo che dovrebbe essere soppresso]
È possibile eliminare un nodo senza ottenere il nodo precedente, avendo essa imitare il seguente nodo e l'eliminazione che uno invece:
void delete(Node *n) {
if (!is_sentinel(n->next)) {
n->content = n->next->content;
Node *next = n->next;
n->next = n->next->next;
free(next);
} else {
n->content = NULL;
free(n->next);
n->next = NULL;
}
}
Come puoi vedere, dovrai occuparti appositamente dell'ultimo elemento. Sto usando un nodo speciale come nodo sentinella per contrassegnare il finale che ha content e next essere NULL.
UPDATE: le linee Node *next = n->next; n->next = n->next->next mescola sostanzialmente il contenuto del nodo, e libera il nodo: Immagine che si ottiene un riferimento al nodo B da cancellare in:
A /To be deleted
next ---> B
next ---> C
next ---> *sentinel*
il primo passo è n->content = n->next->content: copiare il contenuto delle seguenti nodo al nodo di essere "soppressi":
A /To be deleted
next ---> C
next ---> C
next ---> *sentinel*
Quindi, modificare le next punti:
A /To be deleted
next ---> C /----------------
next ---| C |
next ---> *sentinel*
La realtà è gratuito il seguente elemento, ottenendo al caso finale:
A /To be deleted
next ---> C
next ---> *sentinel*
sensibile e sicura opzione solo sotto tali restrizioni è quello di segnare il nodo cancellato senza realmente scollegamento di esso, rinviando che ad un secondo momento.
Non è l'unica opzione, ma una buona, niente meno che +1. Lo facciamo nel nostro sistema un bel po 'con cancellazioni inutilizzate/differite. – Adisak
Non possibile.
Ci sono hack per simulare la cancellazione.
Ma nessuno di questi cancellerà il nodo puntato dal puntatore.
La soluzione popolare di cancellare il seguente nodo e copiare il suo contenuto al reale nodo da eliminare ha effetti collaterali se avete puntatori esterni che puntano ai nodi nella lista, nel qual caso un il puntatore esterno che punta al nodo seguente diventerà pendente.
È possibile trovare alcune discussioni su SO here.
Node * next = n-> next; n-> next = n-> next-> next; puoi per favore elaborarlo di più? – user215968
Se la lista dei collegamenti è abbastanza lunga, i contenuti di spostamento saranno una soluzione fattibile? – user215968
@ sconosciuto, sì, sarebbe una soluzione fattibile. Questo approccio potrebbe complicare l'aliasing (un altro codice contiene un riferimento ai nodi interessati e così via); ma lo avrai comunque. – notnoop