Listy są prostą i bardzo elastyczną strukturą danych umożliwiającą wykonywanie operacji takich jak

Elementy listy są, tak jak w przypadku stosu, czy kolejki, liniowo uporządkowane ze względu na kolejność ich umieszczania. Rozważa się listy jedno i dwukierunkowe. Listę jednokierunkową będziemy reprezentowali przez obiekt typu LINK, o dwóch atrybutach val- reprezentujący element przechowywanego w liście zbioru, oraz next - dowiązanie do następnego ogniwa listy, o ile istnieje, por. rysunek 6.6(a). Listy dwukierunkowe mają bogatszą strukturę, posiadają bowiem atrybut prev, wskazujący poprzednie ogniwo listy, o ile takie istnieje, por. rysunek 6.6(b)

W niektórych zastosowaniach wygodnie jest używać tzw. list cyklicznych. W takiej liście, wskaźnik next ostatniego ogniwa, wskazuje na początkowe ogniwo listy, a wskaźnik prev pierwszego ogniwa wskazuje na ogniwo ostatnie.

Jako przykład zastosowania, rozważmy zadanie znalezienia wszystkich liczb pierwszych nie większych niż pewna, z góry ustalona, liczba n. Najprostszą metodą rozwiązania tego zadania jest utworzenie tablicy n elementowej i sukcesywne wykreślanie z niej liczb podzielnych przez dwa, trzy itd. Prowadzi to do algorytmu zwanego sitem Eratostenesa, zapisanym tu jako Sito1.

W przedstawionym algorytmie n jest liczbą naturalną, a tab jest tablicą o n rozmiarze n. Pozycje elementów "wykreślonych" z tablicy są zaznaczone zerem.

Sito1{
	for i := 2 to n do tab[i] := i od;	// inicjalizacja tablicy tab
	for i := 2 to n do
	if (tab[i] ¹ 0) then	// o ile i nie było skreślone
	for j := i+1 to n do
	if (tab[j] mod i = 0) then tab[j] := 0; fi	// skreślanie liczb podzielnych przez i
	od;
	fi
	od;
}

Poprawność algorytmu jest dość oczywista, ponieważ wszystkie liczby, podzielne przez liczby mniejsze niż n są zastąpione zerami. Po wykonaniu algorytmu wystarczy wybrać te pozycje, które nie są zerami i są to wszystkie liczby pierwsze mniejsze niż n.

Tablica nie jest w tym przypadku wygodną strukturą danych, gdyż nieinteresujące nas pozycje, wypełnione zerami, nie tylko zajmują miejsce, ale także zmuszają nas do wielokrotnego wykonywania testu (tab[i] ¹ 0). Co więcej, dla tych pozycji wykonujemy niepotrzebnie instrukcję "if (tab[j] mod i = 0) then tab[j] := 0; fi". Unikniemy tego problemu, jeśli użyjemy innej struktury danych.

Strukturą danych w tym algorytmie będzie lista. Każda liczba od 2 do n zostanie początkowo umieszczona na tej liście. W i-tym etapie algorytmu będziemy usuwali ogniwa listy zawierające liczby podzielne przez i. Dzięki temu lista sukcesywnie zmniejsza się, a jej stan końcowy to wszystkie liczby pierwsze mniejsze niż n.

Sito2{
	L := new LINK(2); x := L;	1	// inicjalizacja listy
	for i := 3 to n do x.next := new LINK(i); x := x.next od;	2	// utworzenie listy
	x := L;	3
	while (x ¹ null) do	4
	w := x.val;	5	//badamy podzielność przez kolejną liczbę
	poprzedni := x; y := x.next;	6
	while (y ¹ null) do	7	//przeszukiwanie listy w celu usunięcia liczb podzielnych przez w
	if (y.val mod w = 0) then	8
	poprzedni.next := y.next;	9	//omijamy liczbę podzielną przez w
	else	10
	poprzedni := y;	11
	fi;	12
	y := y.next;	13
	od;	14
	x := x.next;	15
	od;	16
}

Jak to działa? Pętla w linii 2 tworzy listę złożoną z wszystkich liczb naturalnych od 2 do n. Pętla główna, w liniach od 4 do 16, sprawdza podzielność przez kolejną liczbę naturalną. Samo usuwanie (omijanie) niepotrzebnych ogniw listy wykonuje pętla wewnętrzna w liniach 7-14. W tym celu używamy zmiennej y wskazującej aktualnie rozważany element listy, i pomocniczej zmiennej poprzedni, wskazującej zawsze poprzedzający y element.

A jaki jest koszt tego algorytmu? Oczywiste oszacowanie górne liczby wykonanych instrukcji, to S _i=2...n (n-i), co daje Q(n²) operacji. Jest jednak pewien problem. Złożoność algorytmu zwykle wyrażamy jako funkcję rozmiaru danych. Jaki jest więc rozmiar danych w tym przypadku? Jedyną daną do tego algorytmu jest liczba n. Jako rozmiar danych możemy przyjąć, np. liczbę bitów potrzebną do zapisania liczby n (tzn. lg n). Niech więc k będzie rozmiarem danych. Wtedy algorytm wykona 2^2k operacji. Zatem koszt algorytmu Sito jest wykładniczy.

Uwaga Pętle główne w obu algorytmach nie muszą być kontynuowane, jeżeli dojdziemy do elementu n/2. Co więcej, pętla wewnętrzna też może zostać skrócona: w przebiegu badającym podzielność przez w, nie musimy sprawdzać liczb większych od n/w.

Pytanie 4: Jaki jest minimalny koszt połączenia dwóch list o długości n i m?