Kompiuterių moksle duomenų struktūra - tai reikšmių ir informacijos organizavimas ir įgyvendinimas. Paprasčiau tariant, duomenų struktūra yra būdas efektyviai organizuoti duomenis. Duomenų struktūros skiriasi nuo abstrakčių duomenų tipų tuo, kaip jos naudojamos. Duomenų struktūros - tai abstrakčių duomenų tipų įgyvendinimas konkrečioje ir fizinėje aplinkoje. Jos tai daro naudodamos algoritmus. Tai matyti iš sąrašo (abstraktaus duomenų tipo) ir susieto sąrašo (duomenų struktūros) santykio. Sąraše yra verčių arba informacijos bitų seka. Susietajame sąraše tarp kiekvieno informacijos mazgo taip pat yra "rodyklė" arba "nuoroda", kuri nurodo į kitą elementą ir ankstesnį elementą. Tai leidžia eiti sąraše pirmyn arba atgal. Be to, duomenų struktūros dažnai optimizuojamos tam tikroms operacijoms atlikti. Geriausios duomenų struktūros paieška sprendžiant problemą yra svarbi programavimo dalis. Duomenų struktūra - tai sistemingas būdas saugoti duomenis.

Kas yra duomenų struktūra ir ADT

Abstraktus duomenų tipas (ADT) apibrėžia, kokias operacijas galima atlikti su duomenų rinkiniu (pvz., įterpimas, skaitymas, ištrynimas). Duomenų struktūra yra konkreti to ADT įgyvendinimo forma programavimo kalboje ar atmintyje (pvz., masyvas, susietasis sąrašas, heš lentelė). ADT orientuoja į elgesį ir sąsają, o duomenų struktūra – į vidinę organizaciją ir atminties išdėstymą.

Pagrindiniai duomenų struktūrų tipai

  • Linijiniai: masyvai (array), susietieji sąrašai (single/double linked list), stekas (stack), eilė (queue), deque.
  • Medžių struktūros: binariniai medžiai, binariniai paieškos medžiai (BST), AVL, Raudona–juoda medžiai, segmentiniai medžiai, B-medžiai.
  • Grafai: reprezentuojami sąsajų sąrašais arba adjacencijos matricomis; naudojami tinkluose ir priklausomybių modeliuose.
  • Heš lentelės (hash tables): spartus rakto–reikšmės atvaizdavimas su vidutinybe ir konfliktų sprendimais (open addressing, chaining).
  • Kaupyklos ir prioritetai: krūvos (heap / priority queue) — naudojamos greitam maksimumo/minimumo paieškai.
  • Tries ir specializuotos struktūros: prefiksų medžiai (trie) tekstiniams duomenims, bloom filtrai (tikimybinės), disjoint-set (Union-Find).

Pavyzdžiai ir charakteristikos

  • Masyvas — duomenys saugomi nuoseklioje atminties vietoje. Greita atsitiktinė prieiga (O(1)), bet brangu dydžio keitimas (O(n) perkopijavimas).
  • Susietasis sąrašas — elementai susieti rodyklėmis. Greita įterpimas/ištrynimas viduryje (O(1) su nuoroda), bet lėtesnė atsitiktinė paieška (O(n)).
  • Stekas ir eilė — specializuoti sąrašų variantai FIFO/FILO operacijoms; paprasta ir efektyvu.
  • Heš lentelė — vidutiniškai O(1) paieška/įterpimas; priklauso nuo gero hešavimo funkcijos ir užpildymo faktoriaus.
  • Medžiai — hierarchinė struktūra, efektyvi paieškai, įterpimui ir rūšiavimui (palyginant su balansavimo mechanizmais: O(log n)).
  • Grafai — modeliuoja sąveikas; algoritmai kaip BFS, DFS, Dijkstra ar Floyd–Warshall sprendžia paiešką, trumpiausius kelius ir kt.

Įprastos operacijos ir algoritmai

  • Paieška — sekveninė paieška (O(n)), binarinė paieška masyve (O(log n)), paieška BST (O(h)).
  • Rūšiavimas — algoritmai (quick sort, merge sort, heap sort) naudoja skirtingas struktūras: masyvus, krūvas, rekursiją.
  • Traversavimas — medžių/graph naršymas: pre-order, in-order, post-order; grafų: BFS (lygiai), DFS (stogas/rekursija).
  • Prioritetų tvarkymas — krūvos ir prioritetinės eilės leidžia efektyviai pasirinkti didžiausią/mažiausią elementą; naudojama Dijkstra algoritmoje.
  • Hešavimas — spartina rakto–reikšmės operacijas; svarbu spręsti kolizijas.
  • Disjoint-set — jungimosi ir radimo operacijos (Union-Find) su keliais heuristikos pagerinimais (path compression) — beveik amortizuotas O(α(n)).

Kompleksijos (Big‑O) — trumpas orientyras

  • Masyvas: prieiga O(1), paieška O(n), įterpimas/ištrynimas O(n) (puslapyje).
  • Susietasis sąrašas: prieiga O(n), įterpimas/ištrynimas O(1) (turint mazgą).
  • Heš lentelė: paieška/įterpimas vidutiniškai O(1), blogiausiu atveju O(n).
  • Binarinis paieškos medis (balansuotas): paieška/įterpimas/ištrynimas O(log n).
  • Krūva: įterpimas O(log n), ištraukimas max/min O(log n).

Pasirinkimas ir praktinės pastabos

  • Rinkitės struktūrą pagal dominančias operacijas: ar dažniausiai skaitote pagal indeksą, ar įterpiate/ištrinate viduryje, ar reikia greitos paieškos pagal raktą?
  • Atsiminkite atminties ir našumo kompromisus: masyvai turi geresnę kaštų lokalizaciją (cache locality), susietieji sąrašai – lankstumą dydžio požiūriu.
  • Balansavimas ir papildomos meta-informacijos saugojimas (pvz., medžių aukštis) gali pagerinti garantuojamą našumą, bet pridėti sudėtingumo implementacijoje.
  • Parallelumas ir sriegių saugumas: kai kurios struktūros reikalauja sinchronizacijos ar spausdinimo mechanizmų.
  • Praktinės sritys: duomenų bazės, tinklai, operacinės sistemos, paieškos varikliai, žaidimų varikliai ir kt. vis remiasi tinkamu duomenų struktūrų pasirinkimu.

Geros praktikos patarimai

  • Pradėkite nuo paprastesnės struktūros ir profiliuokite programą — tik tada optimizuokite.
  • Naudokite jau patikrintas bibliotekas (standartines kolekcijas), jei įmanoma; jos dažnai optimizuotos ir patikrintos.
  • Išmokite atpažinti ADT reikalavimus: ar jums reikia sąrašo, masyvo, žemėlapio (map), rinkinį (set) ar prioriteto eilės?
  • Testuokite ribinius atvejus: tuščias rinkinys, vienas elementas, didelis duomenų kiekis; matuokite ir analizuokite atminties naudojimą.

Apibendrinant: duomenų struktūra yra sistemingas būdas saugoti duomenis ir užtikrinti, kad reikalingos operacijos būtų atliekamos efektyviai pagal konkrečius programos reikalavimus. Tinkamai parinkta ir įgyvendinta duomenų struktūra kartu su efektyviais algoritmais yra kertinis gero ir našaus programavimo pagrindas.