Ero sivun ”Linkitetty lista” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p solmulinkki muutettu |
jutellaan "kilpailevasta toteutustavasta" jotain vielä |
||
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 [[C plus plus|C++]]-kielissä linkitetyt listat
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.
[[Luokka:Tietorakenteet]]
[[de:Liste (Datenstruktur)]]
| |||