ALG 5

5.1 Listy jednokierunkowe 95

w tej książce dla uproszczenia operuje się głównie wartościami typu int, co nie umniejsza bynajmniej ogólności wywodu. Ewentualne przeróbki tak uproszczonych algorytmów należąjuż raczej do „kosmetyki” niż do zmian o charakterze zasadniczym.

Idea jest zatem następująca: jeżeli lista jest pusta, to struktura informacyjna zawiera dwa wskaźniki NULL. Na rysunkach znajdujących się w tej książce, wartość NULL będzie od czasu do czasu zaznaczana jako OOOOh adres pamięci równy zero. Warto jednak pamiętać, że w ogólnym przypadku NULL nie jest bynajmniej równa zeru - jest to pewien adres, na który na pewno żadna zmienna nie wskazuje (taka jest ogólna idea wskaźnika NULL, niestety wielu programistów o tym nie pamięta). Pierwszy element listy jest złożony z jego własnej wartości (informacji do przechowania) oraz ze wskaźnika na drugi element listy. Drugi zawiera własne pole informacyjne i, oczywiście, wskaźnik na trzeci element listy itd. Miejsce zakończenia listy' zaznaczamy poprzez wartość specjalną NULL. Spójrzmy na rysunek 5-2 przedstawiający listę złożoną z trzech elementów': 2, -I2,1

INFO

Rys. 5 - 2.

Przykład listy jednokierunkowej

Oh

Rysunek 5-3 jest dokładnym odbiciem swojego poprzednika — z tą ty lko różnicą, że w miejsce strzałek symbolizujących „wskazywanie” są użyte konkretne wartości liczbowe adresów komórek pamięci. Heksadecymalna liczba umieszczona nad rekordem jest adresem w pamięci komputera, pod którym zostało mu przydzielone miejsce przez standardową procedurę new¹.

Wróćmy jeszcze do analizy rekordów składających się na listę. Pole głowa struktury informacyjnej wskazuje na komórkę zawierającą 2 pierwszy element listy), czyli - wyrażając się czytelniej - zawiera adres, pod którym w pamięci komputera jest zapamiętany rekord.

1

Ze względów' historycznych w'arto może przypomnieć, że w klasycznym języku C trzeba było w celu przydzielania pamięci używać funkcji bibliotecznych calloc i malloc. W C++ instrukcja new robi dokładnie to samo, lecz o wiele czytelniej, i stanowi już element języka.