Taulukko (tietorakenne)

Läpikäynti

Usein taulukon jokaiselle alkiolle halutaan tehdä jotakin. Jos taulukon koko on 6, täytyy käydä läpi indeksit 0..5. Tähän käytetään ohjelmointikielen for-lausetta seuraavaan tapaan:
(i käy läpi arvot 0..5, ja joka arvolla toistetaan sisennettyä lausetta)for i := 0 to 5 do
    tee jotain T[i]:n kanssa
end for
Yleisesti:
T: taulukko
n: taulukon koko
f: funktio, joka tekee jotain alkiolle
for i := 0 to n-1 do
    f(T[i])
end for
Monissa ohjelmointikielissä on myös for each -lause, joka helpottaa taulukon ja muiden säiliöiden läpikäyntiä. Tämä on kuitenkin rajoittuneempaa kuin indeksoiminen: jokainen alkio täytyy käydä läpi, alkion indeksiä ei ole saatavilla ja joissakin ohjelmointikielissä taulukkoon ei voi sijoittaa tällä tavalla.
for each a in T do
    f(a)
end for
Funktionaalista ohjelmointia tukevissa kielissä for each voi olla toteutettu korkeamman kertaluvun funktiona eli funktiona, joka saa parametrikseen funktion.
for_each(f, T)

Alkion etsiminen

Yksinkertainen hakualgoritmi on peräkkäishaku, jossa taulukosta etsitään arvo käymällä alkiot yksi kerrallaan läpi. Pseudokoodina:
function peräkkäishaku(T, k, n)
    T: taulukko
    k: haettava arvo
    n: taulukon koko
    jos arvo löytyy, palauttaa etsityn arvon indeksin (ensimmäisen vastaan tulevan)
    jos arvoa ei löydy, palauttaa -1
    
    for i := 0 to n-1 do
        if T[i] = k then return i
    end for

    (ei löytynyt)

    return -1
end function
Jos taulukko on järjestetty, voidaan käyttää tehokkaampaa puolitushakua.

Koon kasvattaminen

Taulukon kokoa ei varsinaisesti voi kasvattaa, mutta vanhan taulukon alkiot voi kopioida uuteen, suurempaan taulukkoon. Yleisimmissä ohjelmointikielissä on välineitä, jotka tekevät tämän automaattisesti, esimerkiksi C++:n std::vector ja Javan Vector tai ArrayList.
T: vanha taulukko
S: uusi taulukko
n: vanhan taulukon koko

S := new table(n * 2)
for i := 0 to n - 1 do
    S[i] := T[i]
end for
C-kielessä voidaan yrittää kasvattaa taulukon kokoa, mikä onnistuu vain, jos keskusmuistia on riittävästi vapaana. Jos alkioita joudutaan jatkuvasti lisäämään ja poistamaan, linkitetty lista voi olla parempi tietorakenne.

Alkion lisääminen taulukon alkioiden väliin

Uuden alkion lisääminen taulukon alkioiden väliin (esimerkiksi suuruusjärjestyksen säilyttämistä varten) muistuttaa yllä esitettyä poistoalgoritmia: Alkioita täytyy työntää eteenpäin taulukon loppupäästä alkaen lisäyskohtaan asti. Jos työntämisen aloittaa lisäyskohdasta ja etenee loppua kohden, syntyy virhe: lisäyskohdan alkio kopioituu jokaiseen sitä seuraavaan taulukon paikkaan!
T: taulukko
a: indeksi, johon lisättävä alkio sijoitetaan

kasvata T:n kokoa yhdellä
n := T:n uusi koko

for i := n – 2 down to a do
    T[i + 1] := T[i]
end for
Lisäyslajittelu käyttää hyväkseen yllä esitettyä lisäysalgoritmia.

Muunnelmia

Ohjelmoinnissa taulukoita on kaikkialla, joten niistä on tehty lukuisia muunnelmia.

Moniulotteiset taulukot

Taulukot voivat olla moniulotteisia. Kaksiulotteisuus voidaan toteuttaa taulukolla, jonka alkiot ovat taulukoita:
T := new Table(korkeus)
for i := 0 to korkeus – 1 do
    T[i] := new Table(leveys)
end for
Tämä toteutustapa luonnollisesti mahdollistaa kuinka moniulotteiset taulukot tahansa. Läpikäyntiin voidaan käyttää sisäkkäisiä for-lauseita:
for y := 0 to korkeus – 1
    for x := 0 to leveys – 1
        T[y][x] := 0
    end forend for
Sisäkkäiset taulukot mahdollistavat myös vaikkapa kolmionmuotoisen taulukon, josta voi olla hyötyä esimerkiksi toteutettaessa suuria symmetrisiä matriiseja. Linkitetty lista on yksinkertainen tietorakenne, joka ketjuttaa arvoja toisiinsa hitusen sisäkkäisten taulukoiden tapaan.
Kaksiulotteista taulukkoa voidaan jäljitellä käyttämällä yksiulotteista taulukkoa:
T := new Table(leveys * korkeus)

seuraava vastaa ilmausta T[x][y] := 999
T[y * leveys + x] := 999
Tästä on se etu, että taulukko sijaitsee keskusmuistissa yhtenäisenä nauhana, jolloin välimuistitus saattaa parantua ja taulukon jokaiselle alkiolle on helpompi ja hitusen nopeampi tehdä operaatioita. Usein esimerkiksi bittikarttakuvat ladataan tähän muotoon keskusmuistiin.

Taulukko laitteistoläheisesti

Taulukko on helpoimpia tietorakenteita toteuttaa konekielen tasolla. Itse asiassa keskusmuistia voi ajatella nauhamaisena taulukkona, jota indeksoidaan muistiosoitteilla. Taulukko on vain yhtenäinen pätkä keskusmuistia.

Taulukon luominen

Taulukko luodaan pyytämällä käyttöjärjestelmää varaamaan vapaalta muistialueelta n · k tavua muistia, missä n on taulukon pituus ja k yhden alkion vaatima tila tavuina. Käyttöjärjestelmä vastaa antamalla osoittimen varatun muistialueen alkuun.
Jos taulukon säilyy muistissa koko suorituksen ajan, tarvittava muistialue voidaan sisällyttää ohjelman binääriin. Paikallisena muuttujana käytettävä pieni taulukko voidaan myös luoda ajonaikaiseen pinoon.

Taulukon indeksoiminen

Käyttöjärjestelmän antama osoitin on arvo, joka sisältää taulukon ensimmäisen alkion muistiosoitteen – eli indeksin taulukkoon nimeltä keskusmuisti. Olkoon tuo osoite p. Jos halutaan käyttää taulukon ensimmäistä alkiota johonkin, prosessoria voidaan yksinkertaisesti käskeä noutamaan k tavua pitkä arvo muistiosoitteesta p. Jos halutaan noutaa arvo taulukon indeksistä 3, prosessoria käsketään noutamaan k tavua pitkä arvo osoitteesta p + 3 · k. Tällaista osoitteiden summausta kutsutaan osoitinaritmetiikaksi.

Ohjelmointi ilman taulukoita

Useimmat ohjelmoijat ovat tottuneet käyttämään taulukoita jokapäiväisesti. Kuitenkin monissa funktio-ohjelmointikielissä, kuten LISPissä ja Haskellissa, alkeellisimpana tietorakenteena taulukon tilalla on linkitetty lista. Se sopii kieliin, joissa for-lauseen korvaa rekursio. Jos puhtaassa funktio-ohjelmointikielessä on taulukko, sen muuttaminen voi olla toteutettu käyttäen alkuperäisen taulukon päälle lisättyä hakurakennetta, jolloin indeksointi ei toimikaan vakioajassa.
Lua perustuu assosiaatiotauluun, joka toimii myös taulukkona.