ALG 4

94 Rozdział 5. Struktury danych

5.1. Listy jednokierunkowe

Lista jednokierunkowa jest oszczędną pamięciowo strukturą danych, pozwalającą grupować dowolną — ograniczoną tylko ilością dostępnej pamięci — liczbą elementów: liczb, znaków, rekordów... Jest to duża zaleta w porównaniu z tablicami, których rozmiar co prawda może być określany dynamicznie, ale przydział dużego, „liniowego” obszaru pamięci podczas wykonywania programu nie zawsze musi się zakończyć sukcesem. Nietrudno sobie bowiem wyobrazić, że o wiele bardziej prawdopodobne jest bezproblemowe przydzielenie 50,000 razy pamięci na rekordy 4 bajtowe niż zarezerwowanie miejsca na tablicę zajmującą 200 KB! (W rzeczywistości lista, która pozwala zapamiętać 200 KB informacji zajmuje w' pamięci oprócz owych „gołych” 200 KB pewną dodatkową pamięć. Z każdym rekordem jest związane dodatkowe pole na wskaźnik do kolejnego rekordu listy - patrz rysunek 5-1.

wartość	999
	999
następny ⁹

ELEMENT

Rys. 5 - I.

Typy rekordów używanych podczas programowa nici list.

	9?9
glowct •	W : i : ^ 999
	W : i : ^ 999
ogon •—

INFO

Do budowy listy jednokierunkowej używane są dwa typy „komórek” pamięci. Pierwszy jest zwykłym rekordem natury informacyjnej, zawierającym dwa wskaźniki: do początku i do końca listy'. Drugi typ komórek jest również rekordem, jednakże ma on już charakter roboczy. Zawiera bowiem pole wartości i wskaźnik na następny element listy. W typowych opisach struktur listowych nie wzmiankuje się zazwyczaj rekordu informacyjnego (nie jest on elementem struktury danych) - jest to oczywisty błąd. Kosztem kilku bajtów pamięci’ uzyskujemy bowiem ciągły dostęp do bardzo istotnych operacji i ułatwiamy ogromnie operację podstawową: dołączenie nowego elementu na koniec listy (jeśli nie wstawiamy na koniec listy, to zawsze możemy przyłączyć nowy element na początek listy, ale tracimy wówczas informację o kolejności przybywania danych!).

Pola: głowa, ogon i następny są wskaźnikami', natomiast wartość może być czymkolwiek - liczbą, znakiem, rekordem etc. W przykładach znajdujących się

’ W IBM PC zmienna wskaźnikowa zajmuje 4 lub 8 bajtów w zależności od użytego modelu pamięci.

³ Fakt „wskazywania” na coś jest symbolizowany dalej przez „strzałki”.