Jest pewna bardzo ciekawa sztuczka programistyczna używana czasem przy implementowaniu operacji na listach, a która mi jakoś zupełnie "uciekła" - odkryłem ją dopiero niedawno, powtarzając algorytmy przed egzaminem inżynierskim. Chodzi o tzw. listę z wartownikiem.
Wyobraźmy sobie typową listę łączoną pojedynczo, napisaną w C++. Przykładowa funkcja sprawdzająca, czy szukany element występuje w liście mogłaby wyglądać tak:
bool element_in_list_p(node* startFrom, const element& what)
{
node* iter = startFrom();
while(iter != NULL)
{
if(iter->value == what)
{
return true;
}
iter = iter->next;
}
return false;
}
W każdym obiegu pętli mamy dwa porównania - jedno pilnuje, byśmy nie wyszli poza listę, a drugie sprawdza, czy znaleźliśmy szukany element. Liczba porównań dla n-elementowej listy to 2n.
Gdybyśmy jednak trzymali też wskaźnik na koniec listy, algorytm wyszukujący moglibyśmy przepisać następująco:
bool element_in_list_p(node* startFrom, node* end, const element& what)
{
end->next = new_list_node(what);
node* iter = startFrom();
while(iter->value != what)
{
iter = iter->next;
}
if(iter == end) {
delete_list_node(end->next);
end->next = NULL;
return false;
}
delete_list_node(end->next);
end->next = NULL;
return true;
}
Idea jest bardzo prosta - wstawiamy szukaną wartość na koniec listy - w ten sposób wiemy, że szukana wartość na pewno pojawi się przynajmniej raz, dokładnie na końcu. Możemy więc wyrzucić jedno sprawdzenie w pętli, to odpowiedzialne za pilnowanie, czy nie wyszliśmy poza listę. W ten sposób zmniejszyliśmy liczbę sprawdzeń dla n-elementowej listy z 2n do n+1. Oszczędzamy co prawda tylko na stałej, ale przy bardzo dużych listach może to mieć znaczenie. Żeby ta sztuczka miała sens, musimy oczywiście dysponować wskaźnikiem na koniec listy.