Arvutiteaduses on andmestruktuur viis väärtuste ja teabe organiseerimiseks ja hoidmiseks nii, et seda saaks hiljem efektiivselt kasutada. Lihtsamalt öeldes on andmestruktuur reeglistik ja konkreetne paigutus andmete salvestamiseks mälus või teisel salvestusmeedial. Andmestruktuurid erinevad abstraktsetest andmetüüpidest selle poolest, kuidas neid reaalselt rakendatakse: abstraktne andmetüüp kirjeldab, milliseid operatsioone saab andmete peal teha, aga andmestruktuur on selle abstraktsiooni konkreetne realiseerimine. Andmestruktuurid realiseeritakse sageli koos algoritmide ja mäluhaldusmeetoditega, mis tagavad vajaliku jõudluse. Seda rolli võib hästi näha loendi (abstraktne andmetüüp) ja lingitud loendi (andmestruktuur) vahelises seoses. Nimekiri sisaldab väärtuste või infobittide jada. Seotud loendis on iga infosõlme vahel "osuti" või "viide", mis osutab järgmisele (ja topeltlingitud loendi puhul ka eelmisele) elemendile — see võimaldab liikuda loendis edasi või tagasi. Parima andmestruktuuri valimine probleemi lahendamisel on oluline osa programmeerimisest. Andmestruktuur on süstemaatiline viis andmete säilitamiseks ja nendele operatsioonide (nt lisamine, kustutamine, otsimine, läbikäimine) efektiivseks tegemiseks.

Tüübid ja nende omadused

  • Massiiv (array) — elementide järjestatud ja kontsentreeritud salvestus; kiire juhuslik ligipääs (O(1)), aga väärtuste lisamine või kustutamine keskele võib olla kallis (O(n)). Sobib, kui teada eeldatav suurus või kui vajalik kiire indekseeritud ligipääs.
  • Lingitud loend (linked list) — sõlme-põhine struktuur, kus iga element hoiab väärtust ja viidet järgmisele (või eelnevale) elementidele; lihtne lisada või eemaldada elemendid (O(1) juhul kui viide on olemas), aga juhuslik ligipääs on aeglane (O(n)).
  • Pinu (stack) — LIFO (last-in, first-out) reegli järgi; operaatorid: push, pop, peek. Tihti implementeeritud massiivina või lingitud loendina.
  • Järjekord (queue) — FIFO (first-in, first-out); operaatorid: enqueue, dequeue. Kasulik ülesannetes nagu tööde järjekorrad ja sündmuste käsitlemine.
  • Tärn- ja hulgapuu (tree, e.g. binary tree, BST, heap) — hierarhiline struktuur, kus sõlmedel võivad olla alam-sõlmed; binaarpuu jaotab andmed vasakule/paremale, heap tagab maksimaalse/minimaalse elemendi kiireks leidmiseks.
  • Hajutustabel (hash table) — võtme-põhine otsingutabel, mis kasutab hajutisfunktsiooni (hash) ja lahendab kollisioonid; keskmine ligipääs O(1), halbade hajutiste või kehva kollisioonihaldusega võib märkimisväärselt halveneda.
  • Graf (graph) — sõlmed (tipud) ja servad (ühendused); sobib võrkude, sõltuvuste ja marsruutide modelleerimiseks. Esindatakse tavaliselt naabrusloendite või naabrusmaatriksi abil.

Põhitegevused ja keerukus

Tavalised operatsioonid andmestruktuuride peal on: lisamine, kustutamine, otsimine, järjest läbitungimine (traversal) ja ligipääs indeksile. Iga struktuuri puhul tuleb arvestada nende operatsioonide ajalis-ruumilist keerukust (Big O). Mõned tüüpilised näited:

  • Massiiv: ligipääs O(1), otsimine O(n), sisestus/kustutus keskele O(n).
  • Lingitud loend: lisamine alguses O(1), otsimine O(n), juhuslik ligipääs O(n).
  • Hajutustabel: keskmine otsing/lisamine O(1), halvim O(n) sõltuvalt kollisioonidest.
  • Binaarne otsingupuu (tasakaalustamata): sisestus/otsing O(h), kus h on puu kõrgus; tasakaalustatud puudes (AVL, Red-Black) on see O(log n).
  • Heap: sisestus O(log n), maksimumi/või minimumi leidmine O(1), eemalduse korral O(log n).

Kasutusjuhtumid ja valikukriteeriumid

Andmestruktuuri valikul arvesta järgmiste küsimustega:

  • Millised operatsioonid peavad olema kiireimad? (otsing, lisamine, kustutamine, ligipääs indeksi järgi)
  • Kas andmete hulk muutub dünaamiliselt või on fikseeritud?
  • Kui tähtis on mälu kasutuse efektiivsus ja andmete järjestus?
  • Kas vajad mitut samaaegset ligipääsu või tahad immutabiilset struktuuri (nt funktsionaalset programmeerimist toetavad struktuurid)?

Näiteks, kui pead kiiresti otsima võtme järgi, vali hajutustabel või tasakaalustatud otsingupuu. Kui vajad LIFO-käitumist, kasuta pinu. Kui modelleerid võrgusõlmede suhteid, on graf vajalik koos sobiva esitusviisiga (naabrusloend vs -maatriks).

Praktilised näited

  • Implementatsioon: pinu saab lihtsasti realiseerida massiivina (fikseeritud suurus) või lingitud loendina (dünaamiline). Kui palju push/pop operatsioone ja mälupiiranguid on, määrab valiku.
  • Puud ja traversaalid: binaarse puu jaoks kasutatakse sageli rekursiivset või iteratiivset läbikäiku — inorder, preorder, postorder — sõltuvalt sellest, millist järjekorda andmete töötlemiseks vaja on.
  • Graafialgoritmid: BFS (laiusepõhine otsing) kasutab järjekorda, DFS (sügavuspõhine otsing) kas pinu (rekursiivne või iteratiivne). Need algoritmid näitavad, kuidas andmestruktuurid ja algoritmid koos töötavad.

Hea praktika

  • Kasuta standardseid ja hästi testitud raamatukogusid, kui need olemas on — enamik programmeerimiskeeli pakub optimeeritud andmestruktuure.
  • Hinda jõudlust reaalse töökoormuse alusel (profiling), mitte ainult teoreetiliste hinnangute põhjal.
  • Säilita lihtsus: ära optimeeri enne kui vajalik — selgus ja hooldatavus on tähtsal kohal.
  • Pane tähele mälu- ja konkulentsiaspekte, kui töötad mitme lõimega või suurte andmemassiividega.

Kokkuvõttes on andmestruktuurid programmeerimise ja algoritmide keskne osa: õige valik suurendab rakenduse efektiivsust ja lihtsustab lahenduse ehitamist. Hea arusaam erinevatest tüüpidest, nende omadustest ja kompromissidest aitab leida sobivaima lahenduse konkreetsele probleemile.