Podatkovna struktura

Podatkòvno struktúro dobimo z združevanjem osnovnih podatkovnih tipov. V računalništvu je način shranjevanja podatkov v računalniku, da jih lahko učinkovito uporabimo. Velikokrat bo skrbno izbrana podatkovna struktura omogočila uporabo učinkovitejšega algoritma.

V izdelavi veliko vrst programov bo izbira odgovarjajoče podatkovne strukture osnovni izdelavni premislek, saj so izkušnje pri gradnji velikih sistemov pokazale, da je težavnost izvedbe in kakovost končnega rezultata močno odvisna od izbire najboljše podatkovne strukture. Ko se izberejo podatkovne strukture, postanejo uporabljeni algoritmi sorazmerno očitni. Včasih stvari delujejo v obratni smeri - izberejo podatkovne strukture, ker določene pomembne naloge potrebujejo algoritme, ki najbolje delujejo z določenimi podatkovnimi strukturami, vendar je v obeh primerih izbira primernih podatkovnih struktur odločilna.

Ta vpogled je vodil do veliko določenih izdelavnih postopkov in programskih jezikov v katerih so podatkovne strukture bolj kot algoritmi ključni ureditveni činitelj. Objektno usmerjeni programski jeziki kot sta C++ in Java sta ena skupina jezikov, ki kažeta ta pristop.

Osnovni gradniki večine podatkovnih struktur so polja, zapisi in reference.

Nepopolni seznam podatkovnih struktur

linearne podatkovne strukture
- seznam
  - tabela (polje, vektor)
    - bitne slike
      - slike
      - višinske slike (Heightfields)
  - povezani seznam
    - preskakovalni seznam
- razpršena tabela
- sklad (oziroma LIFO zadnji noter, prvi ven)
- vrsta (oziroma FIFO prvi noter, prvi ven)
  - prednostna vrsta
- dvojna vrsta (Deque)
- izravnalna vrzel
grafovske podatkovne strukture
- seznam sosednosti
- prizorski graf
- drevesne podatkovne strukture
  - B-drevo
  - dvojiško iskalno drevo
    - samoutežno dvojiško iskalno drevo
      - AVL-drevo
      - rdečečrno drevo
      - plosko drevo (Splay tree)
  - kopica
  - drevo izpeljav
  - priponsko drevo
  - (trie)
    - (Patricia trie)
odmišljene podatkovne strukture
- združevalno polje
druge podatkovne strukture
- etiketirana unija (Tagged union)

Glej tudi