Matriisit vs linkitetyt luettelot
Matriisit ovat yleisimmin käytetty tietorakenne elementtikokoelman tallentamiseen. Useimmat ohjelmointikielet tarjoavat menetelmiä, joilla voit helposti ilmoittaa taulukoita ja käyttää taulukoiden elementtejä. Linkitetty lista, tarkemmin sanottuna yksilinkitetty lista, on myös tietorakenne, jota voidaan käyttää elementtikokoelman tallentamiseen. Se koostuu solmusekvenssistä ja jokaisella solmulla on viittaus sekvenssin seuraavaan solmuun.
Kuvassa 1 on koodinpätkä, jota käytetään tyypillisesti taulukon arvojen ilmoittamiseen ja määrittämiseen. Kuva 2 esittää, miltä matriisi näyttäisi muistissa.
Yllä oleva koodi määrittelee taulukon, johon voi tallentaa 5 kokonaislukua ja niihin päästään indekseillä 0-4. Yksi tärkeä taulukon ominaisuus on, että koko taulukko on varattu yhdeksi muistilohkoksi ja jokainen elementti saa oman tilansa taulukossa. Kun taulukko on määritetty, sen koko on kiinteä. Joten jos et ole varma taulukon koosta käännöshetkellä, sinun on määritettävä riittävän suuri taulukko ollaksesi turvassa. Mutta suurimman osan ajasta aiomme itse asiassa käyttää vähemmän elementtejä kuin olemme osoittaneet. Joten huomattava määrä muistia menee hukkaan. Toisa alta, jos "riittävän suuri joukko" ei itse asiassa ole tarpeeksi suuri, ohjelma kaatuu.
Linkitetty lista varaa muistin elementeilleen erikseen omassa muistilohkossaan ja kokonaisrakenne saadaan linkittämällä nämä elementit linkkeinä ketjuun. Jokaisessa linkitetyn luettelon elementissä on kaksi kenttää, kuten kuvassa 3 on esitetty. Datakenttä sisältää todelliset tallennetut tiedot ja seuraava kenttä sisältää viittauksen ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon pääksi.
| data | seuraava |
Kuva 3: Linkitetyn luettelon elementti
Kuva 4 esittää linkitettyä luetteloa, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki elementit paitsi viimeinen tallentavat viittauksen seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavassa kentässään. Mitä tahansa luettelon elementtiä pääsee käsiksi aloittamalla alusta ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.
Vaikka taulukot ja linkitetyt luettelot ovat samank altaisia siinä mielessä, että molempia käytetään elementtikokoelman tallentamiseen, niissä on eroja, jotka johtuvat strategioista, joita ne käyttävät varaamaan muistia elementeilleen. Taulukot varaavat muistin kaikille elementeilleen yhtenä lohkona ja taulukon koko on määritettävä ajon aikana. Tämä tekisi taulukoista tehottomia tilanteissa, joissa et tiedä taulukon kokoa käännöshetkellä. Koska linkitetty lista varaa muistia elementeilleen erikseen, se olisi erittäin tehokas tilanteissa, joissa et tiedä listan kokoa käännöshetkellä. Ilmoittaminen ja linkitetyn luettelon elementtien käyttäminen ei olisi suoraviivaista verrattuna siihen, kuinka käytät suoraan taulukon elementtejä sen indeksien avulla.
