Il modo giusto per rimuovere un elemento da un elenco collegato

Question

Il modo giusto per rimuovere un elemento da un elenco collegato

#1 da (10 voti)
#2 da (9 voti)

8

In questa intervista a Slashdot Linus Torvalds è citato come dicendo:

I've seen too many people who delete a singly-linked list entry by keeping track of the "prev" entry, and then to delete the entry, doing something like

if (prev)
prev->next = entry->next;
else
list_head = entry->next;

and whenever I see code like that, I just go "This person doesn't understand pointers". And it's sadly quite common.

People who understand pointers just use a "pointer to the entry pointer", and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a "*pp = entry->next".

Come sviluppatore di PHP, non ho toccato i puntatori da Introduzione a C in università dieci anni fa. Tuttavia, ritengo che questo sia un tipo di situazione che dovrei almeno conoscere. Di cosa parla Linus? Ad essere onesti, se mi venisse chiesto di implementare un elenco collegato e di rimuovere un elemento, il modo "sbagliato" sopra è il modo in cui lo farei. Che cosa devo sapere per codificare come Linus dice meglio?

Sto chiedendo qui piuttosto che su Stack Overflow perché in realtà non sto riscontrando un problema con questo codice di produzione.

pointers

posta dotancohen 18.02.2015 - 20:49

fonte

2 risposte

10

Esempiodicodice

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

Se abbiamo bisogno di una logica per distruggere il nodo, possiamo semplicemente aggiungere una riga di codice alla fine:

// Deallocate the node which is now stranded from the list.
free(to_remove);

risposta data 05.12.2017 - 06:14

fonte

Leggi altre domande sui tag pointers

Dove devo effettuare la localizzazione (lato server o lato client)? Perché alcune librerie open source mancano di commenti?

score 9 · Accepted Answer

Uso delle mie abilità L331 MS Paint:

La soluzione originale è puntare a Nodi tramite curr . In tal caso, si controlla se il nodo successivo dopo curr ha il valore delete e, in tal caso, reimposta il puntatore curr node next . Il problema è che non esiste un nodo che punta al capo della lista. Ciò significa che deve esserci un caso speciale per controllarlo.

Quello che Linus (probabilmente) propone invece non è di salvare il puntatore sul nodo esaminato corrente, ma piuttosto il puntatore al puntatore al nodo corrente (etichettato pp ). L'operazione è la stessa: se il puntatore pp punta a un nodo con il valore corretto, ripristini il puntatore pp .

La differenza arriva all'inizio della lista. Mentre non c'è nessun nodo che punta alla testa della lista, c'è, in effetti, un puntatore alla testa della lista. Ed è esattamente lo stesso puntatore a un nodo, proprio come un altro puntatore next puntatore. Quindi non c'è bisogno di una clausola speciale per l'inizio della lista.