User:Pomalit/sandbox/Ahelloend
From Wikipedia, the free encyclopedia
Arvutiteaduses, ahelloend (inglise k. linked list) on lineaarne kogum andmeelemente, mille järjekorda ei anna nende füüsiline paigutus mällu. Selle asemel osutab iga element järgmisele. Ahelloend on andmestruktuur, mis koosneb sõlmede kogumist, mis koos esindavad järjestust. Kõige põhilisemal kujul sisaldab iga sõlm: andmeid ja viidet (teisisõnu linki) järjestuse järgmisele sõlmele. See struktuur võimaldab elementide tõhusat sisestamist või eemaldamist järjestuse igast positsioonist iteratsiooni ajal. Keerukamad variandid lisavad täiendavaid linke, võimaldades meelevaldsetes kohtades sõlmede tõhusamat sisestamist või eemaldamist. Ahelloendi puuduseks on see, et juurdepääsuaeg on lineaarne. Kiirem juurdepääs, näiteks juhuslik juurdepääs, pole teostatav. Massiividel on parem vahemälu asukoht ahelloendiga võrreldes.
Ahelloendid kuuluvad kõige lihtsamate ja levinumate andmestruktuuride hulka. Neid saab kasutada mitmete teiste levinud abstraktsete andmetüüpide, sealhulgas loendite, virnade, järjekordade, assotsiatiivsete massiivide ja S-avaldiste rakendamiseks, ehkki pole haruldane rakendada neid andmestruktuure otse ahelloendi aluseta kasutamata.
Ahelloendi peamine eelis tavapärase massiivi ees on see, et loendi elemente saab hõlpsalt lisada või eemaldada ilma kogu struktuuri ümberjaotamata või ümber korraldamata, kuna andmeüksusi ei pea mälus ega kettal järjestikku salvestama. Ahelloendid võimaldavad sõlmede sisestamist ja eemaldamist loendi mis tahes punktis ja võimaldavad seda teha pideva arvu toimingutega, hoides loendi läbimise ajal mälus lingile lisamise või eemaldamise linki eelnevat linki.
Teiselt poolt, kuna lihtsad ahelloendid ei võimalda iseenesest juhuslikku juurdepääsu andmetele ega mis tahes vormis tõhusat indekseerimist, on paljud põhitoimingud - näiteks loendi viimase sõlme hankimine, antud tugipunkti sisaldava sõlme leidmine või uue sõlme sisestamise koha leidmine - võib vajada enamiku või kõigi loendielementide iteratsiooni. Ahelloendite kasutamise eelised ja puudused on toodud allpool. Ahelloendid on dünaamilised, nii et pikkus võib vastavalt vajadusele suureneda või väheneda. Iga sõlm ei pruugi tingimata järgida mälus füüsiliselt eelmist.