Datarakenteet

Datarakenteet ovat ohjelmoinnissa käytettyjä rakenteita, joiden avulla tieto järjestetään ja saavutetaan tehokkaasti. Ne voivat olla abstrakteja tietotyyppejä (ADT) kuten lista, joukko tai kartta sekä konkreettisia toteutuksia kuten taulukot, linkitetyt listat, puut, grafit ja hajautustaulut. Datarakenteiden valinta vaikuttaa suorituskykyyn, muistinkäyttöön ja algoritmien monimutkaisuuksiin.

Lineaariset rakenteet ovat taulukot, jotka tallentavat elementit peräkkäin ja tarjoavat nopean satunnaiskäynnin, mutta koon muuttaminen voi olla kallista. Linkitetyt listat koostuvat solmuista, joissa on viittaukset seuraavaan solmuun; ne mahdollistavat tehokkaan lisäyksen ja poiston. Pino (LIFO) ja jono (FIFO) ovat lineaarisia rakenteita, jotka hallitsevat pääsyjärjestyksen.

Ei-lineaariset rakenteet ja hajautustaulut edustavat monimutkaisempaa järjestystä: puut kuten binääripuut ja tasapainotetut puut (esim. AVL, punamustan puu) mahdollistavat nopean haun, lisäyksen ja järjestetyn läpikäynnin. Grafit mallintavat verkostoja solmujen ja reunojen kautta ja soveltuvat reititys- ja verkkoanalyyseihin. Hajautustaulu tallentaa avain-arvopareja ja tarjoaa yleensä nopean haun sekä lisäyksen, mutta huonoissa tapauksissa suorituskyky voi heikentyä.

Operaatioihin kuuluvat lisäys, poisto, haku ja läpikäynti. Traversal-tekniikat riippuvat rakenteesta: puissa voidaan käyttää pre-, in- ja post-order -läpikäyntiä, grafien läpikäynti sekä reitinetsintä. Datarakenteiden valinta ratkaisee, miten tietoa voidaan tehokkaasti käsitellä sovelluskohtaisissa tehtävissä.