datarakenteiden

Datarakenteet ovat ohjelmoinnissa käytettyjä menetelmiä tietojen tallentamiseen, järjestämiseen ja muokkaamiseen siten, että algoritmit voivat suorittaa tehtäviä tehokkaasti. Ne määrittelevät, miten data on muistissa järjestetty, miten sitä voidaan hakea ja muokata sekä millaisia operaatioita sen päällä voidaan suorittaa.

Yleisimmät datarakenteet voidaan jakaa useisiin luokkiin: taulukot, linkitetyt listat, pinot, jonot, puut, grafit ja hajautustaulukot. Taulukot tarjoavat nopean pääsyn indeksoituun dataan, mutta niiden koon muuttaminen voi olla kallista. Dynaamiset taulukot voivat kasvaa tai pienentyä, mutta suurin osa operaatioista voi aiheuttaa muistisiirtoja. Linkitetyt listat mahdollistavat nopean lisäyksen ja poistamisen ilman suurta muistin järjestelyä, mutta pääsy satunnaiseen alkioon on O(n). Pinoja ja jonoja käytetään järjestäytyneenä tavan käsitellä tapahtumia (LIFO ja FIFO). Puut, kuten binääripuustot ja tasapainotetut puut (AVL, punamustapuut), tukevat tehokasta hakua ja lisäystä logaritmisilla aikavaatimuksilla. Hajautustaulukot tarjoavat usein O(1) pääsyn odotusarvolla, mutta kolarihoito ja hyvän hajautusfunktion suunnittelu ovat tärkeitä.

Graafit kuvaavat monimutkaisempia suhteita ja ne voidaan esittää sekä vieruslistana että vierusmatriisina riippuen tilan ja suorituskyvyn tarpeista.

Datarakenteiden valinta vaikuttaa sekä algoritmien että ohjelman muistinkäyttöön ja suorituskykyyn. Ne kehittyvät jatkuvasti uusien muistinhallintaratkaisujen ja ohjelmistoarkkitehtuurien kehittyessä.