Lista z wartownikiem

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) //doszlismy do konca listy - elementu nie bylo
	{
		delete_list_node(end->next);
		end->next = NULL;
		return false;
	}
	//element znaleziony
	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.