tietorakenteita

Tietorakenteet ovat ohjelmoinnissa käytettyjä rakenteita, joiden avulla tiedot tallennetaan, järjestetään ja hakemaan sekä muokataan tehokkaasti. Ne voivat olla sekä abstrakteja käsitteitä että konkreettisia toteutuksia, ja niiden avulla voidaan optimoida suorituskyky eri tilanteissa. Keskeisiä operaatioita ovat lisäys, poisto, haku ja läpikäynti.

Yleisimmät tietorakenteet ovat taulukot ja listat sekä niiden variaatiot. Taulukko on kiinteäkokoisessa muodossaan peräkkäiseen muistissa tallennettu kokoelma, joka tukee nopeaa satunnaishakua mutta muuttuvan koon toteuttaminen vaatii uuden taulukon. Linkitetty lista koostuu solmuista, joihin liittyy viitteet seuraavaan solmuun, joten lisäykset ja poistot ovat tehokkaita, mutta satunnainen haku on hidas. Pinot (stack) ja jonot (queue) rajoittavat pääsyä: pino on LIFO-tyyppinen ja jono FIFO-tyyppinen. Puu (tree) ja graafi (graph) kuvaavat rakenteita, joissa solmut ovat yhteydessä toisiinsa; puissa on usein mahdollisuus järjestetyyn hakemiseen ja tasapainotetut puut (esim. AVL, punamustapuu) tarjoavat nopeaa hakua. Graafit kuvaavat verkostoja ja reittejä, ja niitä käytetään monenlaisiin verkko- ja reititysongelmiin. Hash-taulu (hash table) mahdollistaa avaimen mukaan hakemisen keskimäärin O(1) -aikaisesti. Setit ja mapsit (kartat) ovat yleisiä kokoelmia uniikkien arvojen tai avain-arvo -parien hallintaan.

Valinta tietorakenteen välillä riippuu halutuista operaatioista, muistin rajallisuudesta ja suorituskykyvaatimuksista sekä siitä, kuinka usein kokoelmaa muokataan. Hyvä suunnittelu huomioi sekä tilan että ajan kompromissit.