Adatszerkezet

Adatszerkezetnek nevezzük a (számítógépes adatfeldolgozás céljaira előállított) adatok tárolási célokat szolgáló strukturális, formai elrendezését.

A számítástechnikában az adatszerkezet az adatok számítógépben való tárolása olyan módon, mely biztosítja azok hatékony használatát. Sokszor egy körültekintően megválasztott adatszerkezet hatékonyabb algoritmusok használatát teszi lehetővé. Az adatszerkezet megválasztása gyakran egy megfelelő absztrakt adatszerkezet megválasztásával kezdődik. A jól megtervezett adatszerkezet számos kritikus művelet végrehajtását teszi lehetővé a lehető legkisebb erőforrásigény – futási idő, tárolóterület – mellett. Az adatszerkezet megvalósítása adattípusok, hivatkozások és egy programnyelv által biztosított, rajtuk elvégzett műveletek felhasználásával történik.

A különböző adatszerkezetek más-más alkalmazásoknál használhatók, közülük némely nagy mértékben bizonyos feladatokra specializált. Például a B-fa különösen jól alkalmazható adatbázisok megvalósítására, míg a irányítótábla (routing table) számítógépek hálózatának működését szabályozza.

Számos programtípus tervezésénél az adatszerkezet megválasztása elsődleges tervezési szempont, mivel a nagy rendszerek kifejlesztésében szerzett tapasztalatok azt mutatják, hogy a megvalósítás nehézsége, és a végeredmény teljesítménye és minősége nagy mértékben a legmegfelelőbb adatszerkezet kiválasztásától függ. Az adatszerkezet megválasztása után már gyakran viszonylag egyértelmű a használandó algoritmus. Van amikor a dolgok fordítva működnek – azért választunk bizonyos adatszerkezetet, mert bizonyos kulcsfeladatok olyan algoritmussal rendelkeznek melyek különleges adatszerkezettel adják a legjobb eredményt.

Ez a felismerés számos olyan formalizált tervezési módszer, programozási nyelv születését hívta elő, amelyekben az adatszerkezet, és nem az algoritmus a szervező kulcstényező. A legtöbb programnyelvre jellemző valamilyen modul rendszer készlet, mely az adaszerkezetek különböző alkalmazásokban való biztonságos újrafelhasználását teszi lehetővé azáltal, hogy azok ellenőrzött megvalósításának (implementáció) részleteit a vezérelt interfész modul mögött rejti el. Az objektumorientáltságot támogató programozási nyelvek, mint például a C++ és a Java erre a célra főleg osztályokat használnak.

Mivel a professzionális programok számára az adatszerkezetek nagyon fontosak, közülük sokat széles körben támogatnak a modern programozási nyelvek és fejlesztői környezetek szabványos könyvtárai, mint például a C++ Szabványos Sablonkönyvtára (Standard Template Library), a Java Alkalmazásfejlesztői Interfész (API) (Application Programming Interface), és a Microsoft .NET framework.

A legtöbb adatszerkezet építőkövei a tömbök, rekordok, változó rekordok, és hivatkozások. Például a nullképes hivatkozás, egy olyan hivatkozás amely lehet akár nullértékű is, a hivatkozások és a változó rekordok egy kombinációja, a legegyszerűbb láncolt adatszerkezet pedig, a láncolt lista, rekordokból és nullképes hivatkozásokból épül fel.

Vita van arról, hogy az adatszerkezetek vajon a program megvalósítását (implementáció) képviselik, vagy csak illesztőegységet (interfész) jelentenek. Ennek eldöntése nézőpont kérdése. Az adatszerkezeteket tekinthetjük úgy, mint két függvény közötti interfész, vagy mint egy módszer olyan tár kezelésének megvalósítására, amely a vonatkozó adattípus szerint van szervezve.

További információk

• Descriptions from the Dictionary of Algorithms and Data Structures
• Hivatkozások a C/C++ Felhasználói Csoportok oldalairól
• Collection of free Data structures e-books