ALG8

108__Rozdział 5. Struktury danych

5.1.3.Listy jednokierunkowe - teoria i rzeczywistość

Oprócz pięknie brzmiących rozważań teoretycznych istnieje jeszcze twarda rzeczywistość, w której... mają wykonywać się nasze pieczołowicie przygotowane programy¹.

Spójrzmy obiektywnie na listy jednokierunkowe pod kątem ich wad i zalet (patrz tabela 5-1).

wady	zalety
nienaturalny dostęp do elementów	małe zużycie pamięci
niełatwe sortowanie	elastyczność

Tabela 5-1.

Wady i zalety list jednokierunkowych,

Przeanalizujmy szczególnie uważnie zagadnienie sortowania danych będących elementami listy. Wyobrażamy sobie zapewne, że posortowanie w pamięci struktury danych, która nie jest w' niej rozłożona liniowo (tak jak ma to miejsce w przypadku tablicy), jest dość złożone.

I ista, do której nowe elementy są wstawiane już na samym początku konsekwentnie w określonym porządku, służy, oprócz swojej podstawowej roli gromadzenia danych, także do ich porządkowania. Jest to piękna właściwość: „sama" struktura danych dba o sortowanie! W sytuacji gdy istnieje tylko jedno kryterium sortowania (np. w kierunku wartości niemalejących pewnego pola a^-), to możemy mówić o ideale. Cóż jednak mamy począć, gdy elementami listy są rekordy o bardziej skomplikowanej strukturze, np.:

struct

(

char imierżO];

char nazwisko[30] ;

int wiek;

int kod_pracownika;

)

Raz możemy zechcieć dysponować taką listą uporządkowaną alfabetycznie, wg nazwisk, innym razem będzie nas interesował wiek pracownika... Czy należy w takim przypadku dysponować dwiema wersjami tych list - co „pożera" cenną pamięć komputera - czy też może zdecydujemy się na sortowanie listy' w' pamięci? Jednak uwaga: to drugie rozwiązanie zajmie z kolei cenny czas procesora!

1

Wbrew wszelkim przesłankom nie jest lo definicja systemu operacyjnego...