linked data structure
Főnév
linked data structure (tsz. linked data structures)
- (informatika) A linked data structure (magyarul: láncolt adatszerkezet) egy olyan adatszerkezeti forma, ahol az egyes elemek (csomópontok) explicit módon mutatnak a következő (vagy akár előző) elem(ek)re egy mutató (pointer) vagy referencia segítségével.
Ez a megközelítés dinamikus memóriahasználatot tesz lehetővé, ellentétben a tömb-alapú struktúrákkal, ahol a méret rögzített vagy előre lefoglalt.
🧱 Általános jellemzők
- Az adatszerkezet elemei nem egymás után következnek a memóriában.
- Minden csomópont tartalmaz:
- Egy adatmezőt
- Egy vagy több mutatót más csomópontokra
🔁 Főbb típusai
| Típus | Leírás |
|---|---|
| Egyszeresen láncolt lista | Minden csomópont a következőre mutat |
| Kétszeresen láncolt lista | Minden csomópont előzőre és következőre is mutat |
| Körkörösen láncolt lista | A lista visszacsatol: utolsó → első |
| Láncolt verem / sor | FIFO vagy LIFO működés láncolt listával |
| Fa (tree) | Minden csomópont több gyerekre mutathat |
| Gráf (graph) | Tetszőleges irányú mutatások (élek) lehetnek |
📦 Egyszeresen láncolt lista például C++-ban:
struct Node {
int data;
Node* next;
};
Node* head = new Node{5, nullptr};
head->next = new Node{10, nullptr};
head->next->next = new Node{20, nullptr};
✅ Előnyök
| Előny | Miért? |
|---|---|
| 📦 Dinamikus méret | Tetszőlegesen nőhet, memóriát csak szükség szerint foglal |
| 🔁 Egyszerű beillesztés/törlés | Középre beszúrás: O(1), ha mutató megvan |
| 🔄 Hatékony adatmozgatás | Nem kell újraallokálni az egész listát, mint tömbnél |
❌ Hátrányok
| Hátrány | Miért probléma? |
|---|---|
| 🐢 Lassú hozzáférés | Nincs közvetlen indexelés (O(n) a get(i)-hez) |
| 💾 Több memória | A pointerek plusz helyet foglalnak |
| 🧩 Bonyolultabb kezelés | Hibakezelés, mutatók figyelése, törlés nehezebb |
🧰 Alkalmazások
- Dinamikus listák, verem/sor
- Hash tábla ütközéskezelés (chaining)
- Fa- és gráf-adatszerkezetek
- Interpreterek, garbage collector rendszerek
📊 Összehasonlítás: Tömb vs. Láncolt adatszerkezet
| Művelet | Tömb | Láncolt lista |
|---|---|---|
| Hozzáférés index alapján | O(1) | O(n) |
| Beszúrás a közepébe | O(n) | O(1) (ha a hely ismert) |
| Törlés | O(n) | O(1) |
| Memóriakezelés | Statikus vagy újraallokálós | Dinamikus |
| Memóriahatékonyság | Jó | Kevésbé jó (pointer overhead) |
✅ Összefoglalás
| Tulajdonság | Láncolt adatszerkezet |
|---|---|
| Dinamikus? | ✅ Igen |
| Indexelhető? | ❌ Nem |
| Könnyen bővíthető? | ✅ Igen |
| Memóriatakarékos? | ⚠️ Nem mindig (pointerek) |
| Adatelérés? | Lassabb, de flexibilis |
- linked data structure - Szótár.net (en-hu)
- linked data structure - Sztaki (en-hu)
- linked data structure - Merriam–Webster
- linked data structure - Cambridge
- linked data structure - WordNet
- linked data structure - Яндекс (en-ru)
- linked data structure - Google (en-hu)
- linked data structure - Wikidata
- linked data structure - Wikipédia (angol)