User:Pomalit/sandbox/Ahelloend
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.
Eelised ja puudused[edit]
Eelised[edit]
• elementide tõhus (püsiva ajaga) lisamine ja eemaldamine
• suurust piiravad ainult arvutimälu maht ja osutite bittide sügavus
• elementide dünaamiline lisamine ja eemaldamine
Puudused
• elemendile otsese juurdepääsu keerukus, nimelt füüsilise aadressi määramine loendis oleva indeksi (järjekorranumbri) järgi
• osutite jaoks kulub lisamälu (osundajad järgmisele ja eelmisele elemendile) (näiteks massiivides pole kursoreid vaja)
• mõned toimingud loenditega on aeglasemad kui massiividega, kuna loendi suvalisele elemendile pääseb juurde ainult läbi kõigi sellele eelnevate elementide
Ahelloendi põhimõisted ja nomenklatuur[edit]
Iga ahelloendi kirjet nimetatakse sageli elemendiks või sõlmeks.Iga sõlme sisaldab järgmise sõlme viidet, nimetatakse tavaliselt järgmiseks lingiks või järgmiseks osutiks. Ülejäänud väljad nimetatakse andmeteks. Loendi “pea” on esimene sõlm. Loendi “saba” võib olla kas loendi ülejäänud kohad pärast “pead” või loendi viimane sõlme.
Ühesuunaline ahelloend
Ühesuunaline ahelloend sisaldab sõlme, millel on andmed ja linki, mis osutab järgmisele sõlmele. Toimingud, mida saab teha ühesuunalise ahelloendites hõlmavad sisestamist, kustutamist ja läbimist.
Kahesuunaline ahelloend
Kahesuunalise ahelloendis sisaldab iga sõlm lisaks järgmise sõlme lingile ka teist linki, mis osutab järjestuse eelmisele sõlmele.
Paljud operatsioonisüsteemid kasutavad kahesuunalised ahelloendeid, et säilitada viited aktiivsetele protsessidele, lõimedele ja muudele dünaamilistele objektidele. [1]
Mitmesuunaline ahelloend
Mitmesuunalise ahelloendis sisaldab iga sõlm kahte või enam linki. Kahesuunalise ahelloendeid võib vaadelda kui mitmesuunaliselt ahelloendite erijuhte.
Ring ahelloend (inglise k. Circular linked list)
Loendi viimases sõlmes on viideks sageli null viide, mis näitab edasiste sõlmede puudumine. Vähem levinud tava on panna linke loendi esimesele sõlmele; sel juhul öeldakse, et tegemus on ring ahelloenduga. Ring ahelloend on ahelloend, kus viimane link osutab esimesele sõlmele.
Ringi kahesuunalise ahelloendi korral osutab esimene sõlm ka loendi viimasele sõlmele.
Ahelloenduga seotud andmestruktuurid[edit]
Nii pinud kui ka järjekorrad rakendatakse sageli ahelloendite abil ja need lihtsalt piiratakse toetatavate toimingud.
Skip loend(inglise k. skip list), on ahelloend suurendatud viideite kihtidega, mis aitab kiiresti üle hüpata suurel hulgal elemente ja seejärel laskuda järgmisele kihile. See protsess jätkub kuni alumise kihini, mis on loend.
Binaarset puud võib vaadelda kui ahelloendi, kus elemendid ise on ahelloendid. Tulemuseks on see, et iga sõlm võib sisaldada viidet esimesele sõlmele või teise ahelloendi, mis koos sisuga moodustavad selle sõlme all olevad alampuud.
Paisktabel võib ahelloendeid kasutada üksuste ahelate salvestamiseks, mis räsivad paisktabeli samale kohale.
Kuhi jagab mõnda ahelloendi järjekorra omadusi, kuid seda rakendatakse peaaegu alati massiivi abil. Sõlmedest sõlmedesse viite asemel arvutatakse järgmise ja eelmise andmeindeks praeguste andmete indeksi abil.