Linkitetty lista

Wikipedia
Loikkaa: valikkoon, hakuun

Tietojenkäsittelytieteessä linkitetty lista on yksi ohjelmoinnissa käytettävistä perustietorakenteista. Se koostuu joukosta 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 hajasaantia. 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- ja C++-kielissä linkitetyt listat on järkevintä toteuttaa osoittimien avulla.

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.


Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.