Ero taulukkojen ja linkitettyjen luetteloiden välillä

Ryhmät vs. linkitetyt luettelot

Taulukot ovat yleisimmin käytetty tietorakenne elementtien kokoelman tallentamiseksi. Useimmat ohjelmointikielet tarjoavat menetelmiä matriisien ja pääsyelementtien ilmoittamiseksi helposti matriiseissa. Linkitetty luettelo, tarkemmin sanottuna erillisesti 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 koodinpätkä, jota käytetään tyypillisesti taulukon arvojen ilmoittamiseen ja määrittämiseen. Kuvio 2 kuvaa kuinka taulukko näyttäisi muistista.

Yllä oleva koodi määrittelee taulukon, joka voi tallentaa 5 kokonaislukua ja niihin päästään indekseillä 0 - 4. Yksi tärkeä taulukon ominaisuus on, että koko taulukko allokoidaan yhtenä muistin lohkona ja jokainen elementti saa oman tilansa taulukossa. Kun taulukko on määritelty, sen koko on kiinteä. Joten jos et ole varma taulukon koosta kokoamishetkellä, joudut määrittelemään riittävän suuren taulukon ollakseen turvallisella puolella. Mutta suurimman osan ajasta käytämme tosiasiassa vähemmän elementtejä kuin olemme osoittaneet. Joten huomattavasti muistia menetetään todella. Toisaalta, jos ”riittävän suuri ryhmä” ei oikeastaan ​​ole riittävän suuri, ohjelma kaatuu.

Yhdistetty luettelo allokoi muistin elementeilleen erikseen omassa muistilohkossaan ja kokonaisrakenne saadaan yhdistämällä nämä elementit ketjun linkkiksi. Jokaisella linkitetyn luettelon elementillä on kaksi kenttää, kuten kuvassa 3. Tietokenttä sisältää todellisen tallennetun datan ja seuraava kenttä viittaa ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon päähän.

Kuva 3: Yhdistetyn luettelon osa

Kuvio 4 kuvaa linkitetyn luettelon, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki elementit, paitsi viimeinen, tallentaa viittauksen seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavassa kentässä. Mihin tahansa luettelon elementtiin pääsee aloittamalla päästä ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.

Vaikka taulukot ja linkitetyt luettelot ovat samanlaisia ​​siinä mielessä, että niitä molempia käytetään elementtien kokoelman tallentamiseen, niihin liittyy eroja strategioista, joita he käyttävät muistin allokoimiseksi sen elementteihin. Taulukot allokoivat muistin kaikille sen elementeille yhtenä lohkona ja taulukon koko on määritettävä ajon aikana. Tämä tekisi taulukot tehottomiksi tilanteissa, joissa et tiedä taulukon kokoa käännöshetkellä. Koska linkitetty luettelo varaa muistin elementeilleen erikseen, se olisi paljon tehokasta tilanteissa, joissa et tiedä luettelon kokoa kokoamishetkellä. Liitetyn luettelon ilmoitusten ja elementtien käyttö ei olisi suoraviivaista verrattuna siihen, kuinka pääset suoraan taulukon elementteihin käyttämällä sen indeksejä.