Eliminazione di qualsiasi nodo da un singolo elenco collegato quando viene fornito solo il puntatore a quel nodo

Question

Questa è una domanda posta in un'intervista.

"Un solo elenco collegato è presente nella memoria È necessario eliminare un nodo. È necessario scrivere una funzione per eliminare quel nodo, che richiede solo l'indirizzo del nodo da eliminare come input e nient'altro (compresa la testa) "

Ho dato la risposta simile a quella che ho risposto nel post seguente - Copiando il contenuto del nodo successivo nel nodo da eliminare e cancellando quello successivo.

Deleting a middle node from a single linked list when pointer to the previous node is not available

Ma l'intervistatore mi ha chiesto ancora una volta, che cosa se mi passate l'indirizzo del ultimo nodo. Gli ho detto, dal momento che il prossimo sarà un NULL, copia quel NULL nel campo dati insieme con l'indirizzo al nodo successivo che è anche NULL. Poi mi ha detto che ci sarà un problema di puntatori penzolanti ... che non ho capito un po '. Qualcuno può gettare luce su questo problema? C'è una soluzione generica a questo?

Aggiornamento (due giorni dopo): Un po 'aggiuntivo. Considerando che non ci sono nodi speciali alla fine della lista. E l'ultimo nodo punta a NULL e se quel nodo è dato come input, come rendere l'ultimo nodo prima punto a NULL. O è impossibile?

poche parole: Se un nodo è dato come input ad una funzione, come rendere il puntatore che fa riferimento a esso, scegliere NULL

Answer 1

ciondolanti Pointer:

(http://en.wikipedia.org/wiki/Dangling_reference)

puntatori ciondolanti e puntatori selvatici in programmazione di computer sono puntatori che non puntano ad una valida oggetto del tipo appropriato. Questi sono casi speciali di violazione della sicurezza della memoria.

puntatori ciondolanti sorgono quando un oggetto viene eliminato o deallocato, senza modificare il valore del puntatore, in modo che il puntatore ancora punti alla locazione di memoria della memoria deallocato. Poiché il sistema può riallocare la memoria precedentemente liberata in un altro processo, se il programma originale quindi dereferenzia il puntatore (ora) pendente, è possibile che si verifichi un comportamento imprevedibile , poiché la memoria potrebbe contenere dati completamente diversi.

Nella sua risposta, per eliminare il nodo dato che effettivamente elimina il prossimo nodo , che potrebbe essere fatto riferimento da un puntatore. Ecco come si presenta il problema del puntatore.

(1) Non ci sono riferimenti esterni all'elenco, come chiarito in una nota. (2) Può sorgere il problema del puntatore, come ha affermato l'intervistatore.

Entrambi (1) e (2) non possono essere corretti allo stesso tempo. Il che significa che c'è un equivoco da qualche parte.

sull'eliminazione l'ultimo nodo:

Ma l'intervistatore mi ha chiesto ancora una volta, che cosa se mi passate l'indirizzo dell'ultimo nodo. Gli ho detto, dal momento che il prossimo sarà un NULL, copiare NULL nel campo dati insieme con l'indirizzo al nodo successivo che è anche NULL.

Penso che si sta confondendo queste due cose: (1) Un puntatore p che punta a NULL, (2) Un nodo lista collegata che ha NULL nel suo campo di dati.

Supponiamo che la struttura dati sia a -> b -> c -> d. Scrivendo NULL sul campo dei dati di s non creerai magicamente un puntatore NULL nel suo campo next.

È possibile eliminare l'ultimo nodo se l'elenco collegato ha sempre un ultimo nodo speciale che non verrà mai eliminato. Ad esempio, a -> b -> c -> d -> LAST dove LAST ha un valore speciale nel suo campo dati che denota che è davvero l'ultimo elemento. Ora per cancellare d, è possibile cancellare ULTIMO e scrivere il valore speciale nel campo dati di d's.

Forse questi sono esattamente ciò che hai cercato di dire durante l'intervista, nel qual caso ci deve essere stato qualche errore di comunicazione tra te e l'intervistatore.

Answer 2

Se vi sono altri elementi che puntano al nodo successivo che vengono copiate al nodo corrente e quindi cancellato, allora questa operazione introdurrà un bug. Quindi nella tua risposta dovresti aver sottolineato che la tua soluzione funziona solo se non ci sono riferimenti esterni alla lista.

La soluzione funziona con l'ultimo nodo solo se la struttura dati è aumentata con un elemento specifico "ultimo nodo". (Se si utilizza Smalltalk, è possibile scrivere self become: nil Nessun'altra lingua ha qualcosa di simile)

No, non esiste una soluzione generica se ci sono riferimenti esterni all'elenco. Penso che l'intervistatore volesse vedere se sei veramente ben informato sull'argomento o stai solo ripetendo una risposta memorizzata.

Answer 3

Passi:

1. Copiare i dati dal nodo (i + 1) al nodo (i)
2. Copia NEXT di secondo nodo (i + 1) in una variabile temporanea.
3. Elimina il secondo nodo (i + 1) // non richiede il puntatore al nodo precedente.

Funzione:

void delete_node(node* node) 
{ 
    node->Data = node->Next->Data; 
    node* temp = node->Next->Next; 
    delete(node->Next); 
    node->Next = temp; 
} 

Answer 4

Probabilmente il vostro elenco di link di traslazione potrebbe essere necessario assumere che qualsiasi nodo che punta a null è null nodo indipendentemente dal valore ...

a->b->c->d->NULL 

così d è il nodo null e il nodo non deve essere considerato come un nodo. in questo modo è possibile risparmiare sull'utilizzo di valori speciali poiché non sono corretti in senso generico. a parte questo non avrete altro modo per il nodo precedente di puntare a null.

Answer 5

quindi dovrebbe esserci un check in programma se il nodo dato è l'ultimo nodo o meno.

void delete_node(node* node1) 
{ 
    node* search=head; 
    if(node1==head) 
    { 
     head=head->next; 
     search->next=NULL; 
     node1->next=NULL; 
    } 
    while(search->next != node1) 
     search=search->next; 
    if(node1->next==NULL) 
    { 
     search->next=NULL; 
    } 
    else 
    { 
     search->next=node1->next; 
     node1->next=NULL; 
    } 
    delete node1; 
} 

Answer 6

public void removeNode(Node node){ 

     /* if no node return null */ 
     if(node==null) return; 

     /* if only 1 node then delete node */ 
     if(node.getNext()==null) { 
      node = null; 
      return ; 
     } 

     /* copy next node data to this node */ 
     node.data = node.getNext().data(); 

     /* store the next next node */ 
     Node second = node.getNext().getNext(); 

     /* remove next node */ 
     removeNode(node.getNext()); 

     /* set the copied node as next */ 
     node.setNext(second); 
    } 

Answer 7

void deleteNode(Node * ptr) 
{ 
    Node *temp = ptr; 
    ptr = ptr->next; 
    temp->data = ptr->data; 
    temp->next = ptr->next; 
    free(ptr); 
} 

non siamo in grado di attraversare lista collegata singolo all'indietro. Cancellare il nodo significa liberare quella memoria. Quindi, copia il contenuto del prossimo nodo su Puntatore Dato (indirizzo di memoria) e libera il nodo successivo. Risolverà il tuo problema .. Grazie ..