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.

pointers

— dotancohen
źródło

Mówi on, że gdy musisz zapisać lokalizację prevzamiast całego węzła, możesz po prostu zapisać lokalizację prev.next, ponieważ to jedyna rzecz, którą jesteś zainteresowany. Wskaźnik do wskaźnika. A jeśli to zrobisz, unikniesz głupoty if, ponieważ teraz nie masz dziwnego przypadku list_headbycia wskaźnikiem spoza węzła. Wskaźnik do nagłówka listy jest wówczas semantycznie taki sam jak wskaźnik do następnego węzła.

— Ordous

@Ordous: Rozumiem, dziękuję. Dlaczego komentarz? To zwięzła, jasna i pouczająca odpowiedź.

— dotancohen

@Ordous Wszystko, co dotyczy tego fragmentu kodu, jest wskaźnikiem, więc jego punkt nie może mieć nic wspólnego z przechowywaniem całego węzła, a nie przechowywaniem do niego wskaźnika.

— Doval

Odpowiedzi:

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

wprowadź opis zdjęcia tutaj

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.

— Ordous
źródło

Ach, rozumiem teraz ... każdego dnia uczysz się czegoś nowego.

— Lawrence Aiello,

Myślę, że opisujesz wszystko poprawnie, ale sugerowałbym, że właściwym rozwiązaniem jest list_headwskazanie czegoś za pomocą nextwęzła, który wskazuje na pierwszy rzeczywisty element danych (i prevzainicjował się na ten sam obojętny obiekt). Nie podoba mi się pomysł prevwskazywania na coś innego rodzaju, ponieważ takie sztuczki mogą wprowadzić niezdefiniowane zachowanie poprzez aliasing i sprawić, że kod będzie niepotrzebnie wrażliwy na układ struktury.

— supercat

@ superuper Właśnie o to chodzi. Zamiast prevwskazywania na Węzły, wskazuje na wskaźniki. Zawsze wskazuje na coś tego samego typu, mianowicie wskaźnik do węzła. Twoja sugestia jest zasadniczo taka sama - prevwskaż coś „z nextwęzłem”. Jeśli odrzucisz powłokę, otrzymasz tylko list_headwskaźnik początkowy . Lub innymi słowy - coś, co jest zdefiniowane tylko przez posiadanie wskaźnika do następnego węzła, jest semantycznie równoważne ze wskaźnikiem do węzła.

— Ordous

@Ordous: To ma sens, choć zakłada to list_headi nextbędzie zawierało ten sam „rodzaj” wskaźnika. Być może nie problem w C, ale być może problematyczny w C ++.

— supercat

@ supercat Zawsze zakładałem, że to „kanoniczna” reprezentacja połączonej listy, niezależna od języka. Ale nie jestem wystarczająco biegły, aby ocenić, czy naprawdę robi to różnicę między C i C ++ i jakie są tam standardowe implementacje.

— Ordous

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