Ahelloend
- Mitte segamini ajada Ahelaloendiga.
Ahelloend on arvutiteaduses lineaarne andmestruktuur, mille elementide järjekord ei sõltu füüsilisest paigutusest mälus, selle asemel osutab iga element järgmisele [1]. Ahelloend 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 abil. 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 (loendite, pinude, järjekordade, assotsiatiivsete massiivide ja S-avaldiste) rakendamiseks.
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 ning võimaldavad seda teha pideva arvu toimingutega.
Teiselt poolt, kuna lihtsad ahelloendid ei võimalda iseenesest juhuslikku juurdepääsu andmetele ega mis tahes vormis tõhusat indekseerimist, mille järelduseks enamik põhitoimingud – loendi viimase sõlme hankimine, antud andmeid sisaldava sõlme või uue sõlme sisestamiskoha leidmine – võivad vajada enamiku või kõigi loendielementide itereerimist. 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 füüsiliselt mälus eelmist järgida.
Eelised ja Puudused muuda
Ahelloendi eelised ja puudused võrreldes teiste andmestruktuuridega.
Eelised muuda
• tõhus (püsiva ajaga) ja dünaamiline elementide lisamine ja eemaldamine;
• suurust piiravad ainult arvutimälu maht ja osutite bittide sügavus.
Puudused muuda
• elemendile juurdepääsu keerukus, nimelt füüsilise aadressi määramine loendis oleva indeksi (järjekorranumbri) järgi
• osutite jaoks kulub lisamälu (link järgmisele ja eelmisele elemendile, mis pole massiivides vajalik);
• 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 muuda
Iga ahelloendi kirjet nimetatakse sageli elemendiks või sõlmeks. Iga sõlm sisaldab viidet järgmisele sõlmele, mida nimetatakse tavaliselt lingiks või osutiks. Ülejäänud väljad nimetatakse andmeteks. Loendi “pea” on esimene sõlm. Loendi “saba” võib olla kas loendi viimane sõlm või loendi ülejäänud sõlmed pärast “pead”.
Ühesuunaline ahelloend
Ühesuunaline ahelloend sisaldab sõlmi, millel on andmed ja link, mis osutavad järgmisele sõlmele. Toimingud, mida saab teha ühesuunalistes ahelloendites, hõlmavad sisestamist, kustutamist ja läbimist.
Kahesuunaline ahelloend
Kahesuunalises 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 kahesuunalisi ahelloendeid, et säilitada viited aktiivsetele protsessidele, lõimedele ja muudele dünaamilistele objektidele[2].
Mitmesuunaline ahelloend
Mitmesuunalises ahelloendis sisaldab iga sõlm kahte või enam linki. Kahesuunalisi ahelloendeid võib vaadelda ka kui mitmesuunaliste ahelloendite erijuhte.
Ringahelloend (ingl Circular linked list)
Loendi viimases sõlmes on viiteks sageli null-viide, mis näitab edasiste sõlmede puudumist. Vähem levinud tava on panna link loendi esimesele sõlmele; sel juhul öeldakse, et tegemist on ringikujulise ahelloendiga või ringahelloendiga. Ringahelloend on ahelloend, kus viimase elemendi link osutab esimesele sõlmele.
Ringi kahesuunalise ahelloendi korral osutab esimene sõlm ka loendi viimasele sõlmele.
Ahelloendiga seotud andmestruktuurid muuda
Nii pinud kui ka järjekorrad rakendatakse sageli ahelloendite abil ja neid piiratakse toetatavate toimingutega.
Ülehüppe loend (ingl skip list), on ahelloend suurendatud viidete kihtidega, mis aitab kiiresti üle suure hulga elementide hüpata ja seejärel laskuda järgmisele kihile. See protsess jätkub kuni alumise kihini, mis on loend.
Kahendpuud võib vaadelda kui ahelloendit, kus elemendid ise on ahelloendid. Tulemuseks on see, et iga sõlm võib sisaldada viidet esimesele sõlmele või teisele ahelloendile, mis koos sisuga moodustavad selle sõlme all olevaid alampuid.
Paisktabel võib ahelloendeid kasutada üksuste ahelate salvestamiseks, mis räsivad paisktabeli samale kohale.
Kuhi jagab mingi ahelloendi järjekorra omadusi, kuid seda rakendatakse peaaegu alati massiivi abil. Sõlmedest sõlmedesse viiva viite asemel arvutatakse järgmise ja eelmise andme indeks praeguste andmete indeksi abil.
| Ahelloend | Massiiv | Dünaamiline massiiv | Kahendpuu | |
|---|---|---|---|---|
| Indekseerimine | Θ(n) | Θ(1) | Θ(1) | Θ(log n) |
| Lisamine / eemaldamine alguses | Θ(1) | N/A | Θ(n) | Θ(log n) |
| Lisamine / eemaldamine alguses | Θ(n) kui element on teadmata
Θ(1) kui element on teadud |
N/A | Θ(1) | Θ(log n) |
| Lisamine / eemaldamine keskel | otsingu aeg + Θ(1)[3] | N/A | Θ(n) | Θ(log n) |
| Raisatud ruum (keskmine) | Θ(n) | 0 | Θ(n)[4] | Θ(n) |
Viited muuda
- ↑ Cormen, Leiserson, Rivest, and Stein (2001). Introduction to Algorithms. The MIT Press.
{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link) - ↑ "Kernel-Mode Basics: Windows Linked Lists". 03.09.2007. Vaadatud 16.05.2021.
- ↑ kjellkod (25.02.2012). "Why you should never, ever, EVER use linked-list in your code again".
- ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine (1999). Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09).
{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link)