Ero sivun ”Linkitetty lista” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p linkki |
Jpk (keskustelu | muokkaukset) p C++ |
||
Rivi 1:
[[tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''linkitetty lista''' on yksi [[ohjelmointi|ohjelmoinnissa]] käytettävistä perustietorakenteista. Se koostuu joukosta [[solmu (tietojenkäsittelytiede)|solmuja]] eli alkioita, jotka sisältävät tietokenttien lisäksi viittauksen (”linkin”) joko seuraavaan solmuun tai seuraavaan ja edelliseen solmuun. Linkitetyissä listoissa solmun voi lisätä ja poistaa vakioajassa, mutta ne eivät mahdollista [[hajasaanti]]a. Linkitetyt listat voivat olla yksisuuntaisia (yhteen suuntaan linkitettyjä), kaksisuuntaisia (kahteen suuntaan linkitettyjä) tai renkaaksi linkitettyjä.
Linkitettyjä listoja pystyy toteuttamaan useimmilla ohjelmointikielillä. [[Lisp]]- ja [[Scheme]]-kielissä tietorakenne ja listaoperaatiot ovat sisäänrakennettuna. [[C-ohjelmointikieli|C]]- ja [[
Yksinkertaisempi listan toteuttamistapa on kiinteä taulukko, jossa solmut on tallennettu peräkkäisiin muistipaikkoihin. Kiinteä taulukkototeutus vie linkitettyyn listaan nähden vähemmän tallennustilaa ja sen lukeminen on käytännössä hieman nopeampaa, mutta lisäys- ja poisto-operaatiot vaativat alkioiden siirtämistarpeesta johtuen lineaarisesti sitä enemmän aikaa, mitä suurempaa listaa käsitellään. Lisäksi muistipaikkojen peräkkäisyysvaatimus voi aiheuttaa ongelmia muistinvarauksen suhteen, mikäli listan suurinta mahdollista kokoa ei ole päätetty etukäteen.
| |||