Właściwy sposób na usunięcie elementu z listy połączonej

W tym wywiadzie dla Slashdot zacytowano Linusa Torvaldsa:

Widziałem zbyt wiele osób, które usuwają pojedynczo połączony wpis na liście, śledząc wpis „poprzedni”, a następnie usuwając wpis, robiąc coś w stylu

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

i ilekroć widzę taki kod, po prostu mówię „Ta osoba nie rozumie wskaźników”. I to niestety dość powszechne.

Ludzie, którzy rozumieją wskaźniki, używają „wskaźnika do wskaźnika pozycji” i inicjują go za pomocą adresu nagłówka list_head. A następnie, gdy przeglądają listę, mogą usunąć wpis bez użycia żadnych warunków, po prostu wykonując polecenie „* pp = entry-> next”.

Jako programista PHP nie dotknąłem wskaźników od czasu wprowadzenia do C na uniwersytecie dziesięć lat temu. Uważam jednak, że jest to rodzaj sytuacji, z którą powinienem przynajmniej się zapoznać. O czym mówi Linus? Szczerze mówiąc, gdybym został poproszony o zaimplementowanie połączonej listy i usunięcie elementu, powyższy „zły” sposób to sposób, w jaki bym to zrobił. Co muszę wiedzieć, aby kodować, jak mówi Linus najlepiej?

Pytam tutaj, a nie o przepełnienie stosu, ponieważ tak naprawdę nie mam z tym problemu w kodzie produkcyjnym.

Używając moich umiejętności L331 MS Paint:

Pierwotnym rozwiązaniem jest wskazywanie węzłów za pośrednictwem curr. W takim przypadku sprawdzisz, czy następny węzeł currma wartość usuwania, a jeśli tak, zresetuj wskaźnik currwęzła next. Problem polega na tym, że nie ma węzła, który wskazywałby na początek listy. Oznacza to, że musi istnieć specjalny przypadek, aby to sprawdzić.

Zamiast tego Linus (prawdopodobnie) proponuje nie zapisanie wskaźnika w bieżącym badanym węźle, ale wskaźnik do wskaźnika do bieżącego węzła (oznaczonego pp). Operacja jest taka sama - jeśli ppwskaźnik wskazuje na węzeł o właściwej wartości, resetujesz ppwskaźnik.

Różnica pojawia się na samym początku listy. Chociaż nie ma węzła, który wskazywałby na początek listy, w rzeczywistości istnieje wskaźnik do nagłówka listy. I to jest tak samo wskaźnik do węzła, jak nextwskaźnik innego węzła . Dlatego nie ma potrzeby stosowania specjalnej klauzuli na początku listy.

Przykład kodu

// ------------------------------------------------------------------
// 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;

Jeśli potrzebujemy trochę logiki, aby zniszczyć węzeł, możemy po prostu dodać wiersz kodu na końcu:

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