Tervetuloa Jan Hakolan toteuttamaan linkitettyjen tietorakenteiden animointiosaan.
Tässä osassa voit edetä animointeihin linkkejä seuraamalla.
Paluut edellisille sivuille onnistuvat selaimen Back-painikkeella.
TIETORAKENTEET
Linkitetty tietorakenne on listan eräs toteutustapa, jossa rakenteen tietoalkiot on talletettu "solmuihin", jotka on linkitetty osoittimilla toinen toisiinsa. Rakenteen alkuun osoittaa osoitin ja viimeinen solmu on maadoitettu osoittimen 0-arvoon. Kuva havainnollistaa perustilannetta. (Ks. Kuva 1.) Linkitetyllä tietorakenteella, on mm. seuraavanlaisia ominaisuuksia: siihen voidaan lisätä alkioita, siitä voidaan ottaa pois alkioita.
Kuva 1. Linkitetyn tietorakenteen peruskuva
Linkitetyn tietorakenteen etuna listan toteuttamisessa (esim. taulukkoon verrattuna) on , että se mahdollistaa hyvin joustavan dynaamisen muistin käytön. Listaa voi kasvattaa ja pienentää solmu kerrallaan, eikä sen koskaan tarvitse varata tilaa, kuin juuri listan koon verran - tosin solmut vaativat tietokentän lisäksi osoitinkentän.
PINORAKENNE
Pino on tietorakenne, jonka perusominaisuus on se, että viimeksi pinoon laitettu tietoalkio saadaan sieltä seuraavaksi pois: Last in First out (LiFo). (Ks. Kuva 2.)
Kuva 2. Pinotietorakenteen peruskuva
Kuvassa kaksi vasemmalla ylhäällä oleva yhtenäisellä viivoituksella piirretty suorakaide kuvaa uuden tietoalkion lisäämistä rakenteeseen. Kun tietoalkio on tallennettu tietokoneen muistiin, siirretään top-osoitin osoittamaan sen muistipaikkaa. Tätä kuvaa yhtenäisellä viivalla piirretty nuoli topista päällimmäiseen suorakaiteeseen. Jotta lista pysyisi ehjänä, on uuteen tietoalkioon lisättävä tieto edellisen tietoalkion sijainnista. Tämä ei näy kuvassa.
Kuvassa kaksi oikealla ylhäällä oleva katkoviivoituksella piirretty suorakaide kuvaa päällimmäisen tietoalkion poistamista rakenteesta. Ennen tietoalkion poistamista tietokoneen muistista, on top-osoitin siirrettävä osoittamaan seuraavaa tietoalkiota. Tätä kuvaa katkoviivalla piirretty nuoli.
