6 tietorakennetta jokaisen ohjelmoijan tulisi tietää

Polku osaavaksi ja menestyväksi ohjelmoijaksi on vaikea, mutta se on varmasti saavutettavissa. Tietorakenteet ovat ydinkomponentti, joka jokaisen ohjelmointiopiskelijan on hallittava, ja on mahdollista, että olet jo oppinut tai työskennellyt joidenkin perustietorakenteiden, kuten taulukoiden tai luetteloiden, kanssa.

Haastattelijoilla on tapana kysyä mieluummin tietorakenteisiin liittyviä kysymyksiä, joten jos valmistaudut työhaastatteluun, sinun on päivitettävä tietorakenteiden tuntemusta. Lue, kun luettelemme ohjelmoijien ja työhaastattelujen tärkeimmät tietorakenteet.

Linkitetyt listat ovat yksi perustietorakenteista ja usein opiskelijoiden lähtökohta useimmilla tietorakennekurssien kursseilla. Linkitetyt luettelot ovat lineaarisia tietorakenteita, jotka mahdollistavat peräkkäisen datan käytön.

Linkitetyn luettelon elementit tallennetaan yksittäisiin solmuihin, jotka on yhdistetty (linkitetty) osoittimilla. Voit ajatella linkitettyä listaa solmuketjuna, joka on kytketty toisiinsa eri osoittimien kautta.

Aiheeseen liittyvä: Johdatus linkitettyjen luetteloiden käyttöön Javassa

Ennen kuin pääsemme erityyppisten linkitettyjen luetteloiden yksityiskohtiin, on tärkeää ymmärtää yksittäisen solmun rakenne ja toteutus. Jokaisella linkitetyn luettelon solmulla on vähintään yksi osoitin (kaksoislinkitetyissä luettelosolmuissa on kaksi osoitinta), joka yhdistää sen luettelon seuraavaan solmuun ja itse tietokohteeseen.

Jokaisella linkitetyllä luettelolla on pää- ja häntäsolmu. Yhdellä linkitetyllä listasolmulla on vain yksi osoitin, joka osoittaa ketjun seuraavaan solmuun. Seuraavan osoittimen lisäksi kaksoislinkitetyissä luettelosolmuissa on toinen osoitin, joka osoittaa ketjun edelliseen solmuun.

Linkitettyihin luetteloihin liittyvät haastattelukysymykset liittyvät yleensä tietyn elementin lisäämiseen, etsimiseen tai poistamiseen. Linkitettyyn listaan ​​lisääminen vie O(1) aikaa, mutta poistaminen ja haku voi viedä O(n) aikaa pahimmassa tapauksessa. Joten linkitetyt luettelot eivät ole ihanteellisia.

2. Binääripuu

Binääripuut ovat puuperheen tietorakenteen suosituin osajoukko; binääripuun elementit on järjestetty hierarkiaan. Muita puita ovat AVL-, puna-mustat, B-puut jne. Binääripuun solmut sisältävät tietoelementin ja kaksi osoitinta jokaiseen lapsisolmuun.

Jokaisella binaaripuun yläsolmulla voi olla enintään kaksi alisolmua, ja jokainen lapsisolmu voi puolestaan ​​olla kahden solmun yläsolmu.

Aiheeseen liittyvä: Aloittelijan opas binääripuihin

Binäärihakupuu (BST) tallentaa tiedot lajiteltuun järjestykseen, jossa elementit, joiden avainarvo on pienempi kuin ylätason solmu tallennetaan vasemmalle, ja elementit, joiden avainarvo on suurempi kuin pääsolmun avainarvo, tallennetaan oikein.

Binääripuita kysytään usein haastatteluissa, joten jos olet valmistautumassa haastatteluun, sinun tulee tietää, miten binääripuu litistetään, etsitään tietty elementti ja paljon muuta.

3. Hash-taulukko

Hash-taulukot tai hash-kartat ovat erittäin tehokas tietorakenne, joka tallentaa tiedot taulukkomuodossa. Jokaiselle tietoelementille on määritetty ainutlaatuinen indeksiarvo hash-taulukossa, mikä mahdollistaa tehokkaan haun ja poistamisen.

Hajautuskartan avainten määrittämistä tai kartoittamista kutsutaan hajautusprosessiksi. Mitä tehokkaampi hash-toiminto, sitä parempi itse hash-taulukon tehokkuus.

Jokainen hash-taulukko tallentaa tietoelementit arvo-indeksi-parina.

Missä arvo on tallennettava tieto ja indeksi on yksilöllinen kokonaisluku, jota käytetään elementin yhdistämiseen taulukkoon. Hash-funktiot voivat olla hyvin monimutkaisia ​​tai hyvin yksinkertaisia ​​riippuen hajautustaulukon vaaditusta tehokkuudesta ja siitä, kuinka ratkaiset törmäykset.

Törmäyksiä syntyy usein, kun hash-funktio tuottaa saman kuvauksen eri elementeille; hash-kartan törmäykset voidaan ratkaista eri tavoilla käyttämällä avointa osoitusta tai ketjutusta.

Hash-taulukoilla tai hash-kartoilla on useita erilaisia ​​sovelluksia, mukaan lukien kryptografia. Ne ovat ensisijainen tietorakenne, kun tarvitaan lisäystä tai etsintää vakio-O(1)-ajassa.

4. Pinot

Pinot ovat yksi yksinkertaisimmista tietorakenteista, ja niitä on melko helppo hallita. Pinotietorakenne on pohjimmiltaan mikä tahansa tosielämän pino (ajattele laatikoiden tai laattojen pinoa) ja toimii LIFO- (Last In First Out) -tavalla.

Pinon LIFO-ominaisuus tarkoittaa, että viimeksi lisättyäsi elementtiä käytetään ensimmäisenä. Et voi käyttää pinon ylimmän elementin alapuolella olevia elementtejä poksaamatta elementtejä sen yläpuolelle.

Pinoilla on kaksi päätoimintoa: push ja pop. Pushilla elementti lisätään pinoon, ja pop poistaa pinosta ylimmän elementin.

Heillä on myös runsaasti hyödyllisiä sovelluksia, joten haastattelijoille on hyvin yleistä kysyä pinoihin liittyviä kysymyksiä. Pinon kääntämisen ja lausekkeiden arvioinnin osaaminen on varsin välttämätöntä.

5. Jonot

Jonot ovat samanlaisia ​​kuin pinot, mutta ne toimivat FIFO- (First In First Out) -tavalla, mikä tarkoittaa, että voit käyttää aiemmin lisäämiäsi elementtejä. Jonotietorakenne voidaan visualisoida minkä tahansa tosielämän jonona, johon ihmiset sijoitetaan saapumisjärjestyksensä perusteella.

Jonon lisäystoimintoa kutsutaan jonoksi, ja elementin poistamista/poistamista jonon alusta kutsutaan jonon purkamiseksi.

Aiheeseen liittyvä: Aloittelijan opas jonojen ja prioriteettijonojen ymmärtämiseen

Prioriteettijonot ovat olennainen jonojen sovellus monissa tärkeissä sovelluksissa, kuten suorittimen ajoituksessa. Prioriteettijonossa elementit järjestetään niiden prioriteetin mukaan saapumisjärjestyksen sijaan.

6. Kasoja

Kasat ovat eräänlainen binääripuu, jossa solmut on järjestetty nousevaan tai laskevaan järjestykseen. Vähimmäiskeossa ylätason avainarvo on yhtä suuri tai pienempi kuin sen lapsien avainarvo, ja juurisolmu sisältää koko keon vähimmäisarvon.

Vastaavasti Max-keon juurisolmu sisältää keon suurimman avainarvon; sinun on säilytettävä min/max-keon ominaisuus koko kasassa.

Aiheeseen liittyvä: Kasat vs. Pinot: mikä erottaa ne toisistaan?

Kasoilla on runsaasti käyttökohteita niiden erittäin tehokkaan luonteen vuoksi; ensisijaisesti prioriteettijonot toteutetaan usein kasojen kautta. Ne ovat myös keskeinen komponentti kasalajittelualgoritmeissa.

Opi tietorakenteet

Tietorakenteet voivat aluksi tuntua tuskallisilta, mutta niihin on käytettävä riittävästi aikaa, ja ne ovat helppoja.

Ne ovat olennainen osa ohjelmointia, ja melkein jokainen projekti edellyttää niiden käyttöä. On tärkeää tietää, mikä tietorakenne on ihanteellinen tietylle skenaariolle.

7 algoritmia, jotka jokaisen ohjelmoijan tulisi tietää

Nämä algoritmit ovat välttämättömiä jokaisen ohjelmoijan työnkulussa.

Lue Seuraava

Kirjailijasta