6 andmestruktuuri, mida iga programmeerija peaks teadma

Tee oskuslikuks ja edukaks programmeerijaks on keeruline, kuid kindlasti saavutatav. Andmestruktuurid on põhikomponent, mida iga programmeerimisõpilane peab valdama, ja on tõenäoline, et olete juba õppinud või töötanud mõne põhilise andmestruktuuriga, nagu massiivid või loendid.

Intervjueerijad eelistavad küsida andmestruktuuridega seotud küsimusi, nii et kui valmistute tööintervjuuks, peate värskendama oma teadmisi andmestruktuuride kohta. Lugege edasi, kui loetleme programmeerijate ja tööintervjuude jaoks kõige olulisemad andmestruktuurid.

Lingitud loendid on üks elementaarsemaid andmestruktuure ja sageli enamiku andmestruktuuride kursuste õpilaste lähtepunkt. Lingitud loendid on lineaarsed andmestruktuurid, mis võimaldavad andmetele järjestikust juurdepääsu.

Lingitud loendis olevad elemendid salvestatakse üksikutesse sõlmedesse, mis on osutite abil ühendatud (lingitud). Lingitud loendist võib mõelda kui sõlmede ahelast, mis on üksteisega erinevate osutite kaudu ühendatud.

Seotud: Sissejuhatus lingitud loendite kasutamiseks Javas

Enne eri tüüpi lingitud loendite üksikasjadesse jõudmist on oluline mõista üksiku sõlme struktuuri ja rakendamist. Igal lingitud loendi sõlmel on vähemalt üks osuti (kahekordselt lingitud loendi sõlmedel on kaks osutit), mis ühendab selle loendi järgmise sõlme ja andmeüksuse endaga.

Igal lingitud loendil on pea ja saba sõlm. Ühe lingiga loendi sõlmedel on ainult üks osuti, mis osutab ahela järgmisele sõlmele. Lisaks järgmisele osutile on topeltlingitud loendi sõlmedel veel üks osuti, mis osutab ahela eelmisele sõlmele.

Lingitud loenditega seotud intervjuuküsimused keerlevad tavaliselt konkreetse elemendi sisestamise, otsimise või kustutamise ümber. Lingitud loendisse sisestamine võtab O(1) aega, kuid kustutamine ja otsimine võib halvimal juhul O(n) aega võtta. Seega ei ole lingitud loendid ideaalsed.

2. Binaarne puu

Binaarsed puud on puude perekonna andmestruktuuri kõige populaarsem alamhulk; binaarpuu elemendid on paigutatud hierarhiasse. Muud tüüpi puud hõlmavad AVL-i, puna-must-, B-puud jne. Binaarpuu sõlmed sisaldavad andmeelementi ja kahte osutit igale alamsõlmele.

Igal binaarpuu vanemsõlmel võib olla maksimaalselt kaks alamsõlme ja iga alamsõlm võib omakorda olla kahe sõlme vanemsõlme.

Seotud: Kahekomponentsete puude juhend algajatele

Binaarne otsingupuu (BST) salvestab andmed sorteeritud järjestuses, kus elemendid, mille võtmeväärtus on väiksem kui põhiväärtus sõlm salvestatakse vasakule ja elemendid, mille võtmeväärtus on suurem kui vanemsõlme, salvestatakse õige.

Intervjuudes küsitakse tavaliselt kahendpuid, nii et kui valmistute intervjuuks, peaksite teadma, kuidas kahendpuud tasandada, otsida konkreetset elementi ja palju muud.

3. Räsi tabel

Räsitabelid või räsikaardid on väga tõhus andmestruktuur, mis salvestab andmed massiivivormingus. Igale andmeelemendile määratakse räsitabelis ainulaadne indeksi väärtus, mis võimaldab tõhusat otsimist ja kustutamist.

Räsikaardil võtmete määramise või vastendamise protsessi nimetatakse räsimiseks. Mida tõhusam on räsifunktsioon, seda parem on räsitabeli enda efektiivsus.

Iga räsitabel salvestab andmeelemendid väärtus-indeksi paarina.

Kus väärtus on salvestatavad andmed ja indeks on kordumatu täisarv, mida kasutatakse elemendi tabelisse vastendamiseks. Räsifunktsioonid võivad olla väga keerulised või väga lihtsad, olenevalt räsitabeli nõutavast tõhususest ja sellest, kuidas te kokkupõrkeid lahendate.

Kokkupõrked tekivad sageli siis, kui räsifunktsioon loob erinevate elementide jaoks sama vastenduse; räsikaardi kokkupõrkeid saab lahendada erineval viisil, kasutades avatud adresseerimist või aheldamist.

Räsitabelitel või räsikaartidel on palju erinevaid rakendusi, sealhulgas krüptograafia. Need on esimese valiku andmestruktuur, kui on vaja sisestada või otsida konstantse O(1) ajaga.

4. Virnad

Virnad on üks lihtsamaid andmestruktuure ja neid on üsna lihtne hallata. Virna andmestruktuur on sisuliselt mis tahes tegelik virn (mõelge kastide või plaatide virnale) ja see toimib LIFO (Last In First Out) viisil.

Stacksi LIFO atribuut tähendab, et esimesena pääseb juurde viimati sisestatud elemendile. Te ei pääse juurde virna ülemise elemendi all olevatele elementidele ilma selle kohal olevaid elemente hüppamata.

Virnadel on kaks peamist toimingut – push ja pop. Push kasutatakse elemendi sisestamiseks virna ja pop eemaldab virnast kõige ülemise elemendi.

Neil on ka palju kasulikke rakendusi, mistõttu on väga tavaline, et intervjueerijad esitavad virnadega seotud küsimusi. Teadmine, kuidas virna ümber pöörata ja väljendeid hinnata, on üsna oluline.

5. Järjekorrad

Järjekorrad on sarnased virnadega, kuid töötavad FIFO (First In First Out) viisil, mis tähendab, et pääsete juurde varem sisestatud elementidele. Järjekorra andmestruktuuri saab visualiseerida kui mis tahes reaalset järjekorda, kuhu inimesed paigutatakse nende saabumisjärjekorra alusel.

Järjekorra sisestamise toimingut nimetatakse järjekorraks ja elemendi kustutamist/eemaldamist järjekorra algusest nimetatakse järjekorrast eemaldamiseks.

Seotud: Juhend algajatele järjekordade ja prioriteetsete järjekordade mõistmiseks

Prioriteetsed järjekorrad on järjekordade lahutamatu rakendus paljudes olulistes rakendustes, näiteks protsessori ajastamises. Prioriteedijärjekorras järjestatakse elemendid nende prioriteedi, mitte saabumise järjekorra järgi.

6. Kuhjad

Kuhjad on kahendpuu tüüp, kus sõlmed on paigutatud kasvavas või kahanevas järjekorras. Minimaalses kuhjas on vanema võtmeväärtus võrdne selle alamväärtusega või väiksem ja juursõlm sisaldab kogu kuhja minimaalset väärtust.

Samamoodi sisaldab Max Heap juursõlm kuhja maksimaalset võtmeväärtust; peate säilitama min/max hunniku omaduse kogu kuhja ulatuses.

Seotud: Kuhjad vs. Virnad: mis neid eristab?

Kuhjadel on nende väga tõhusa olemuse tõttu palju rakendusi; peamiselt rakendatakse prioriteetsed järjekorrad sageli hunnikute kaudu. Need on ka kuhjade sortimisalgoritmide põhikomponent.

Õppige andmestruktuure

Andmestruktuurid võivad alguses tunduda ahistavad, kuid pühendavad neile piisavalt aega ja need on lihtsad.

Need on programmeerimise oluline osa ja peaaegu iga projekt nõuab nende kasutamist. Oluline on teada, milline andmestruktuur on antud stsenaariumi jaoks ideaalne.

7 algoritmi, mida iga programmeerija peaks teadma

Need algoritmid on iga programmeerija töövoo jaoks olulised.

Loe edasi

Autori kohta