Taulukot vs. linkitetyt luettelot
Taulukot ovat yleisimmin käytetty tietorakenne elementtien kokoelman tallentamiseen. Useimmat ohjelmointikielet tarjoavat menetelmiä matriisien ja pääsyelementtien ilmoittamiseen matriiseissa. Linkitetty luettelo, tarkemmin sanottuna yksittäin linkitetty luettelo, on myös tietorakenne, jota voidaan käyttää elementtien kokoelman tallentamiseen. Se koostuu solmujen sarjasta, ja jokaisella solmulla on viittaus sekvenssin seuraavaan solmuun.
Kuvassa 1 on koodikappale, jota käytetään tyypillisesti taulukon ilmoittamiseen ja määrittämiseen. Kuva 2 kuvaa, kuinka taulukko näyttäisi muistissa.
Koodin yläpuolella määritetään taulukko, joka voi tallentaa 5 kokonaislukua, ja niihin pääsee indekseillä 0–4. Taulukon yksi tärkeä ominaisuus on, että koko taulukko allokoidaan yhtenä muistilohkona ja jokainen elementti saa oman tilansa ryhmässä. Kun matriisi on määritelty, sen koko on kiinteä. Joten jos et ole varma taulukon koosta kääntämisajankohtana, joudut määrittelemään tarpeeksi suuren taulukon ollaksesi turvallisella puolella. Mutta useimmiten aiomme käyttää vähemmän elementtejä kuin olemme jakaneet. Joten huomattava määrä muistia on todella hukkaan. Toisaalta, jos”riittävän suuri taulukko” ei ole oikeastaan tarpeeksi suuri, ohjelma kaatuu.
Linkitetty luettelo jakaa muistin elementteilleen erikseen omassa muistilohkossaan, ja kokonaisrakenne saadaan yhdistämällä nämä elementit ketjun linkkeinä. Jokaisella linkitetyn luettelon elementillä on kaksi kenttää, kuten kuvassa 3 on esitetty. Tietokenttä pitää sisällään varsinaiset tiedot ja seuraava kenttä sisältää viitteen ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen osa tallennetaan linkitetyn luettelon päähän.
Kuva 3: Linkitetyn luettelon osa
Kuva 4 kuvaa linkitettyä luetteloa, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki paitsi viimeinen elementit viittaavat seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavalla kentällä. Mihin tahansa luettelon elementtiin pääsee aloittamalla päästä ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.
Vaikka matriisit ja linkitetyt luettelot ovat samanlaisia siinä mielessä, että molempia käytetään elementtien kokoelman tallentamiseen, niillä on eroja niiden strategioiden vuoksi, joita he käyttävät muistin jakamiseen sen elementteihin. Matriisit varaavat muistin kaikille sen elementeille yhtenä lohkona, ja ryhmän koko on määritettävä ajon aikana. Tämä tekisi matriiseista tehottomia tilanteissa, joissa et tiedä taulukon kokoa kääntöhetkellä. Koska linkitetty luettelo jakaa muistin elementteilleen erikseen, se olisi paljon tehokasta tilanteissa, joissa et tiedä luettelon kokoa kääntöhetkellä. Ilmoitus ja linkitetyn luettelon elementtien käyttäminen eivät olisi suoraviivaisia verrattuna siihen, miten pääset suoraan matriisin elementteihin sen indeksien avulla.
