taulukkorakenteilla

Taulukkorakenteilla tarkoitetaan tietorakenteita, jotka perustuvat taulukon kaltaiseen, muistissa peräkkäin sijaitsevaan tallennustilaan. Tämä mahdollistaa nopean pääsyn elementteihin indeksin perusteella ja hyvän muistihallinnan cache-yhteensopivuuden vuoksi. Koko voi olla kiinteä tai dynaaminen; kiinteäkokoisissa taulukoissa tila varataan etukäteen, kun taas dynaamisissa taulukoissa kapasiteettia voidaan kasvattaa lisäyksen yhteydessä.

Yleisimpiä taulukkorakenteita ovat kiinteäkokoiset taulukot ja dynaamiset taulukot. Monidimensionaaliset taulukot tallentavat useita ulottuvuuksia, esimerkiksi matriisit, jotka koostuvat yhden tai useamman taulukon rivistöistä. Käytännössä taulukkorakenteet tarjoavat nopean O(1) pääsyn indeksiin sekä muistitehokkuutta, mutta niillä on rajoituksia: kiinteäkokoisissa taulukoissa koko on rajoitettu ja dynaamisissa taulukoissa kapasiteetin kasvattaminen saattaa johtaa kopiointiin ja uudelleenallokointiin.

Operaatioiden aikavaikutukset: pääsy on O(1). Lisääminen ja poisto lopussa on amortisoidusti O(1), mutta keskeltä tai alkuun tehtävät muutokset voivat olla O(n). Monidimensionaaliset taulukot lisäävät kompleksisuutta, mutta niitä käytetään usein tallentamaan matriiseja ja taulukkokohtaisia data-rakenteita. Esimerkkejä ohjelmointikielissä ovat C/C++-taulukot, Java-taulukot ja Pythonin listat (jotka ovat käytännössä dynaamisia taulukoita).

Taulukkorakenteiden valinta riippuu sovelluksesta: tarvitsetko nopeat yksittäisvalinnat, ennustettavan muistinkäytön tai peruslikid? Taulukot sopivat, kun määrä muuttuu vähän ja kun muistivälit sekä suorituskyky ovat tärkeitä, mutta ne voivat olla epätaloudellisia, kun koko on epävarma ja lisäys/poisto tapahtuu usein keskeltä.