6 struktura podataka koje bi svaki programer trebao znati

Put do stručnog i uspješnog programera je težak, ali je svakako ostvariv. Strukture podataka temeljna su komponenta koju svaki student programiranja mora ovladati, a velike su šanse da ste već naučili ili radili s nekim osnovnim strukturama podataka kao što su nizovi ili liste.

Anketari više vole postavljati pitanja vezana uz strukture podataka, pa ako se pripremate za razgovor za posao, morat ćete nadopuniti svoje znanje o strukturama podataka. Čitajte dalje dok navodimo najvažnije strukture podataka za programere i razgovore za posao.

Povezani popisi jedna su od najosnovnijih struktura podataka i često početna točka za studente u većini kolegija struktura podataka. Povezani popisi su linearne strukture podataka koje omogućuju sekvencijalni pristup podacima.

Elementi unutar povezanog popisa pohranjeni su u pojedinačnim čvorovima koji su povezani (povezani) pomoću pokazivača. Povezani popis možete zamisliti kao lanac čvorova koji su međusobno povezani putem različitih pokazivača.

Povezano: Uvod u korištenje povezanih popisa u Javi

Prije nego što uđemo u specifičnosti različitih vrsta povezanih popisa, ključno je razumjeti strukturu i implementaciju pojedinačnog čvora. Svaki čvor na povezanom popisu ima barem jedan pokazivač (dvostruko povezani čvorovi popisa imaju dva pokazivača) koji ga povezuje sa sljedećim čvorom na popisu i samom stavkom podataka.

Svaki povezani popis ima glavni i repni čvor. Jednopovezani čvorovi popisa imaju samo jedan pokazivač koji pokazuje na sljedeći čvor u lancu. Uz sljedeći pokazivač, dvostruko povezani čvorovi popisa imaju još jedan pokazivač koji pokazuje na prethodni čvor u lancu.

Pitanja za intervju povezana s povezanim popisima obično se vrte oko umetanja, pretraživanja ili brisanja određenog elementa. Umetanje u povezani popis traje O(1) vremena, ali brisanje i pretraživanje mogu potrajati O(n) vremena u najgorem slučaju. Dakle, povezane liste nisu idealne.

2. Binarno stablo

Binarna stabla su najpopularniji podskup strukture podataka obitelji stabala; elementi u binarnom stablu raspoređeni su u hijerarhiji. Ostale vrste stabala uključuju AVL, crveno-crna, B stabla, itd. Čvorovi binarnog stabla sadrže element podataka i dva pokazivača na svaki podređeni čvor.

Svaki roditeljski čvor u binarnom stablu može imati najviše dva podređena čvora, a svaki podređeni čvor, zauzvrat, može biti roditelj za dva čvora.

Povezano: Vodič za početnike za binarna stabla

Binarno stablo pretraživanja (BST) pohranjuje podatke u sortiranom redoslijedu, gdje elementi s ključ-vrijednošću manjim od nadređenog čvor pohranjeni su na lijevoj strani, a elementi s ključ/vrijednost većim od roditeljskog čvora pohranjeni su na pravo.

Binarna stabla se obično pitaju u intervjuima, pa ako se spremate za intervju, trebali biste znati kako izravnati binarno stablo, potražiti određeni element i još mnogo toga.

3. Hash tablica

Hash tablice ili hash karte su vrlo učinkovita struktura podataka koja pohranjuje podatke u formatu niza. Svakom elementu podataka dodjeljuje se jedinstvena vrijednost indeksa u hash tablici, što omogućuje učinkovito pretraživanje i brisanje.

Proces dodjele ili mapiranja ključeva u hash mapi naziva se raspršivanjem. Što je hash funkcija učinkovitija, to je bolja učinkovitost same hash tablice.

Svaka hash tablica pohranjuje elemente podataka u par vrijednost-indeks.

Gdje je vrijednost podaci koji se pohranjuju, a indeks je jedinstveni cijeli broj koji se koristi za mapiranje elementa u tablicu. Hash funkcije mogu biti vrlo složene ili vrlo jednostavne, ovisno o potrebnoj učinkovitosti hash tablice i kako ćete riješiti kolizije.

Kolizije često nastaju kada hash funkcija proizvodi isto preslikavanje za različite elemente; Kolizije hash mapa mogu se riješiti na različite načine, korištenjem otvorenog adresiranja ili ulančavanja.

Hash tablice ili hash karte imaju niz različitih aplikacija, uključujući kriptografiju. Oni su struktura podataka prvog izbora kada je potrebno umetanje ili pretraživanje u konstantnom O(1) vremenu.

4. Stogovi

Stogovi su jedna od jednostavnijih struktura podataka i prilično ih je lako svladati. Struktura podataka stog je u biti bilo koji stog iz stvarnog života (mislite na hrpu kutija ili ploča) i djeluje na LIFO (Last In First Out) način.

Svojstvo LIFO Stacksa znači da će se prvi pristupiti elementu koji ste zadnji umetnuli. Ne možete pristupiti elementima ispod gornjeg elementa u hrpi bez iskakanja elemenata iznad njega.

Stogovi imaju dvije primarne operacije—push i pop. Push se koristi za umetanje elementa u stog, a pop uklanja najviši element iz hrpe.

Imaju i dosta korisnih aplikacija, pa je vrlo uobičajeno da anketari postavljaju pitanja vezana uz hrpe. Vrlo je bitno znati kako preokrenuti stog i procijeniti izraze.

5. Redovi

Redovi su slični stogovima, ali djeluju na način FIFO (prvi ušao prvi), što znači da možete pristupiti elementima koje ste ranije umetnuli. Struktura podataka reda može se vizualizirati kao bilo koji red u stvarnom životu, gdje su ljudi pozicionirani na temelju njihovog redoslijeda dolaska.

Operacija umetanja u red se naziva red čekanja, a brisanje/uklanjanje elementa s početka reda se naziva dequeuing.

Povezano: Vodič za početnike za razumijevanje redova i prioritetnih redova

Prioritetni redovi su integralna primjena redova u mnogim vitalnim aplikacijama kao što je zakazivanje CPU-a. U prioritetnom redu, elementi su poredani prema njihovom prioritetu, a ne prema redoslijedu dolaska.

6. Hrpe

Hrpe su vrsta binarnog stabla gdje su čvorovi raspoređeni uzlaznim ili silaznim redoslijedom. U minimalnoj hrpi, ključna vrijednost roditelja jednaka je ili manja od one njegovih djece, a korijenski čvor sadrži minimalnu vrijednost cijele hrpe.

Slično, korijenski čvor maksimalne hrpe sadrži maksimalnu vrijednost ključa hrpe; morate zadržati min/max svojstvo hrpe u cijeloj hrpi.

Povezano: Hrpe vs. Stogovi: što ih izdvaja?

Hrpe imaju mnogo aplikacija zbog svoje vrlo učinkovite prirode; prvenstveno, prioritetni redovi se često implementiraju kroz hrpe. Oni su također temeljna komponenta u algoritmima heapsortiranja.

Naučite strukture podataka

Strukture podataka se u početku mogu činiti mučnima, ali posvetite dovoljno vremena i naći ćete ih lake kao kolač.

Oni su vitalni dio programiranja i gotovo svaki projekt zahtijevat će da ih koristite. Ključno je znati koja je struktura podataka idealna za dati scenarij.

7 algoritama koje bi svaki programer trebao znati

Ovi algoritmi su neophodni za rad svakog programera.

Pročitajte dalje

O autoru