previous next Up Title Contents Index

Linkitetyt listat

Listan taulukkototeutusta parempi ratkaisu on antaa listan koon vaihdella mielivaltaisesti, jolloin lista ei koskaan varaa muistista tilaa enempää kuin on tarpeen. Toisaalta lista voi kasvaa niin suureksi kuin on tarvetta (edellyttäen, että muistia on tarpeeksi).

Tällaisessa ratkaisussa tarvitaan edellisessä luvussa käsiteltyä dynaamista muistinhallintaa. malloc()-funktiolla voidaan muistista varata tilaa uusille lista-alkioille aina, kun sellaiseen on tarvetta. Kun alkio on olemassa, se voidaan liittää olemassa olevaan listaan. Kun alkio poistetaan listasta, sen varaamaa tilaa ei enää tarvita. Tila voidaan vapauttaa funktiolla free().

Alkion liittäminen listaan edellyttää alkioiden linkitystä toisiinsa, mikä tarkoittaa sitä, että

edellinen alkio tietää, missä seuraava alkio on.

Tämä voidaan toteuttaa liittämällä kuhunkin alkioon (alkiot ovat tietueita) linkkikenttä, joka on osoitin seuraavaan lista-alkioon (osoitin on käytännössä muistiosoite). Näin saadaan alkio, jota voidaan kuvata graafisesti esimerkiksi seuraavasti:

Kuva
Listan alkio C:n tietueena
Lista on pointteri 1.lista-alkioon

previous next Up Title Contents Index