datarakenteissa

Datarakenteet ovat ohjelmoinnissa käytettyjä rakenteita, joiden avulla tiedot tallennetaan ja järjestetään siten, että niitä voidaan hakea, lisätä tai muuttaa mahdollisimman tehokkaasti. Datarakenteet vaikuttavat sekä sovelluksen suorituskykyyn että muistinkäyttöön, ja niiden valinta riippuu tiedon luonteesta sekä odotetusta operaatioiden kuormituksesta.

Yleisimmät datarakenteet ja niiden tyypilliset ominaisuudet: taulukot (arrays) tarjoavat nopean indeksoinnin O(1), mutta lisäykset ja poistot keskeltä voivat olla kalliita; linkitetyt listat (linked lists) mahdollistavat dynaamisen koon ja O(1) lisäyksen/poiston, mutta haun kustannus on O(n). Pinoja (stack) ja jonoja (queue) käytetään niille tarkoitukseen, että toiminnot seuraavat tiettyä järjestystä; perustoiminnot ovat tavallisesti O(1). Puut (trees) kuten binääriset tai tasapainoiset puut (AVL, Red-Black) tukevat hakua, lisäystä ja poistamista yleensä O(log n). Graafit (graafit) kuvaavat solmujen välistä yhteyttä ja niitä tallennetaan yleisesti naapuriluetteloina tai matriisina; niillä toteutetaan reititys- ja verkkoalgoritmeja. Hajautustaulut (hash tables) tarjoavat keskimäärin O(1) aikaiset hakut ja lisäykset sekä poistot, mutta huonoissa tapauksissa kustannus voi olla O(n). Joukot (sets) ja kartat (maps) voivat rakentua hajautustauluista tai tasapainoisista puista ja tarjoavat tehokkaan jäsenyyden tarkistamisen sekä avaimen mukaista hakemista.

Data- ja sovelluskohtaiset tekijät, kuten tiedon koko, muistinvaraus, käytettävissä olevat kirjastot sekä odotetut operaatioiden suhteet vaikuttavat valintaan. Oikea datarakenne parantaa sekä suorituskykyä että ohjelmiston ylläpidettävyyttä, ja usein käytetään useita rakenteita yhdessä ratkaisemaan ongelmia.