Listtyypit

Listtyypit ovat erilaisten listojen toteutuksia tai rakennetyyppejä, joita käytetään järjestettyjen alkioiden tallentamiseen. Lista on yleisesti järjestetty kokoelma, jonka alkioille pääsee suhteellisella indeksillä ja jonka avulla voidaan suorittaa lisäyksiä, poistoja sekä haun. Eri toteutukset vaikuttavat siihen, millaisia operaatioita voidaan suorittaa tehokkaasti ja miten paljon muistia ne vievät. Listtyypit jaotellaan sekä sen mukaan, miten alkiot tallennetaan, että miten niitä hallitaan ja ylläpidetään.

Yksi keskeinen jaottelu on taulukkoon perustuvaan listaan, eli dynaamiseen taulukkoon. Siinä alkiot tallennetaan taulukkoon, jonka koko kasvaa tarvittaessa. Pääsy indekseihin on O(1); lisäykset loppuun ovat amortisoidusti O(1), mutta suurten lisäysten yhteydessä koko taulukkoa joudutaan mahdollisesti laajentamaan ja kopioimaan.

Toinen päätyyppi on yksisuuntainen linkitetty lista, jossa jokaisella solmulla on viite seuraavaan solmuun. Lisäykset ja poistot alussa ovat nopeita, mutta tietyn kohdan hakeminen vaatii kävelyä, jolloin sen kompleksisuus on O(n).

Kaksisuuntainen linkitetty lista hyödyntää sekä seuraava- että edellinen-viitteitä, jolloin liikkuminen on joustavampaa ja joissakin operaatioissa nopeampaa. Ympyrälista on lista, jossa viimeinen solmu osoittaa takaisin ensimmäiseen, mikä soveltuu kierroksena toistettaviin tehtäviin kuten ajastettuihin prosesseihin.

Funktionaalisissa kielissä käytetään usein pysyviä eli muuttumattomia listoja, joissa muutoksesta luodaan uusi lista ja vanha säilyy. Listtyyppejä valitaan käyttötarpeen mukaan: taulukkopohjaiset tarjoavat nopean indeksihaun, linkitetyt ovat edullisia lisäyksessä ja poistossa, ympyrälistat tukevat kierroksia, ja immutabiliteetti helpottaa rinnakkaisuutta.