40 najboljih pitanja i odgovora za intervju s povezanom listom (2026.)

By: Sarah Chen Sarah Chen
Hours Ažurirano

Pitanja i odgovori za intervju s najpopularnijim linkovima

Priprema za intervju za strukturu podataka zahtijeva fokus na izazove. Pitanja za intervju s povezanom listom otkrivaju dubinu rješavanja problema, logiku pokazivača, svjesnost o pamćenju i kako kandidati rasuđuju kroz rubne slučajeve.

Savladavanje povezanih popisa otvara uloge u različitim proizvodnim timovima, platformama i sistemskom inženjerstvu. Praktično iskustvo gradi snažnu tehničku stručnost, analitičko razmišljanje i čiste navike kodiranja. Od početnika do starijih profesionalaca, ovaj skup vještina podržava stvarno otklanjanje pogrešaka, analizu performansi, mentoriranje mlađih studenata i suradnju s menadžerima na skalabilnim rješenjima koristeći napredne koncepte iz iskustva. Čitaj više…

👉 Besplatno preuzimanje PDF-a: Povezani popis pitanja i odgovora za intervju

Pitanja i odgovori za intervju s najpopularnijim linkovima

1) Objasnite što je povezana lista i kako se razlikuje od niza.

A povezan popis je linearna struktura podataka u kojoj su elementi, nazvani čvorovi, povezani pomoću pokazivača ili referenci. Svaki čvor sadrži podatke i pokazivač/referencu na sljedeći čvor na popisu. Za razliku od nizova, povezani popisi ne pohranjuju elemente u susjednu memoriju.

Ključne razlike između povezane liste i niza:

svojstvo Povezani popis Poredak
Dodjela memorije Dinamičan statički
Vrijeme pristupa elementu O (n) O (1)
Umetanje/brisanje Učinkovit (na bilo kojoj poziciji) Skupo (potrebno premještanje)
Opterećenje memorije Dodatni prostor za pokazivače Nema dodatnog pokazivača iznad glave

Ukratko, povezane liste žrtvuju brže umetanje i dinamičko dimenzioniranje za sporiji nasumični pristup i dodatno opterećenje memorijom zbog pokazivača.

2) Koje su različite vrste povezanih popisa?

Postoje nekoliko vrsta povezanih lista, a anketari vas često traže da ih razlikujete:

  • Jednostruko povezana lista: Svaki čvor pokazuje samo na sljedeći čvor.
  • Dvostruko povezani popis: Čvorovi imaju dva pokazivača: jedan na sljedeći i jedan na prethodni čvor.
  • Kružna povezana lista: Posljednji čvor pokazuje natrag na prvi čvor, tvoreći petlju.
  • Dvostruko kružna povezana lista: Kombinira kružne i dvostruko povezane liste.

Svaka vrsta ima različite slučajeve upotrebe na temelju potreba za prolaskom i memorijom. Na primjer, dvostruko povezane liste omogućuju jednostavno prolaženje unatrag po cijenu dodatnih pokazivača.

3) Kako obrnuti jednostruko povezanu listu? (Pristup kodiranju)

RevKorištenje povezane liste klasično je pitanje na intervjuu. Cilj je promijeniti smjer pokazivača tako da se lista obrne na mjestu bez dodjeljivanja novih čvorova.

Ključna ideja:
Koristite tri pokazivača — prev, curri next — i iterirajte kroz popis. U svakom koraku preusmjerite curr.next do prev, zatim pomaknite sve pokazivače naprijed.

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev; // New head
}

Ovo transformira povezanu strukturu bez dodatnog prostora i pokreće se O (n) vrijeme.

4) Objasnite tehniku ​​​​dvostrukog pokazivača za pronalaženje sredine povezane liste.

Najučinkovitiji način za pronalaženje srednjeg čvora povezane liste je korištenje dva pokazivača:

  • A spori pokazivač pomiče jedan čvor odjednom.
  • A brzi pokazivač pomiče dva čvora odjednom.

Kada brzi pokazivač dođe do kraja, spori pokazivač će biti na sredini. Ova tehnika djeluje u O (n) vrijeme bez dodatnog prostora.

5) Kako biste otkrili ciklus u povezanoj listi?

Detekcija ciklusa je još jedan klasičan problem. Standardno rješenje koristi Floydov algoritam kornjače i zeca:

  • Potez slow pointer korak po korak.
  • Potez fast pointer dva koraka odjednom.
  • Ako lista ima ciklus, dva pokazivača će se susresti.

Ako brzi pokazivač dosegne null, lista nema ciklus. Ova metoda se izvršava u O (n) vrijeme i O (1) prostor.

6) Koje su prednosti i nedostaci povezanih popisa?

Povezane liste nude nekoliko prednosti i nedostataka:

Prednosti Nedostaci
Dinamička veličina Nema slučajnog pristupa
Jednostavno umetanje/brisanje Dodatna memorija za pokazivače
Učinkovito za rastuće podatke Loše performanse predmemorije

Povezane liste dobro funkcioniraju za dinamičke podatke, ali mogu biti sporije od nizova za pristup elementima jer svaki pristup zahtijeva prolazak od početka do kraja.

POVEZANI ČLANCI

7) Kako spojiti dvije sortirane povezane liste?

Spajanje dvaju sortiranih popisa još je jedan čest problem u intervjuu. Ideja je istovremeno proći kroz oba popisa i izgraditi novi sortirani popis odabirom manjeg čvora s bilo kojeg popisa u svakom koraku.

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Ova metoda čuva sortirani redoslijed i izvršava se u O(n + m) vrijeme za liste duljina n i m.

8) Objasnite kako izbrisati N-ti čvor s kraja povezane liste.

Najučinkovitija tehnika koristi dva pokazivača odvojeni s n čvorova. Pomaknite prvi pokazivač za n koraka, a zatim pomaknite oba pokazivača dok prvi ne dođe do kraja. Drugi pokazivač će tada biti neposredno prije ciljnog čvora.

Time se izbjegava zasebno izračunavanje duljine popisa i dovršava se u O (n) vrijeme. Također obrađuje rubne slučajeve poput uklanjanja prvog čvora.

9) Kolika je vremenska složenost pristupa k-tom elementu u povezanoj listi?

Pristupanje datoteci k-ti element u povezanoj listi zahtijeva prolazak od početka dok se ne dođe do k-ti čvor. Budući da povezane liste ne omogućuju izravno indeksiranje, to košta O (n) vrijeme u najgorem slučaju.

Nasuprot tome, nizovi podržavaju izravno indeksiranje u O (1) vrijeme.

10) Zašto biste koristili povezanu listu umjesto niza?

Povezane liste su posebno korisne kada:

  • Očekujete česta umetanja i brisanja na proizvoljnim pozicijama.
  • Ne znate unaprijed veličinu svojih podataka.
  • Fragmentacija memorije otežava kontinuiranu alokaciju memorije.

Podržavaju učinkovitu dinamičku alokaciju memorije i umetanje/brisanje u konstantnom vremenu na kraju liste ili s poznatom referencom čvora - prednosti koje nizovi ne mogu postići.

11) Koje su primjene povezanih popisa u stvarnom svijetu?

Povezane liste se široko koriste u sustavima gdje dinamička dodjela memorije, česta umetanja, ili strukture podataka promjenjive veličine su obavezni. Implementirani su u nekoliko temeljnih koncepata i primjena računalne znanosti kao što su:

  • Dinamičko upravljanje memorijom (koristi se u operativnim sustavima)
  • Funkcije poništavanja/ponovljivanja u uređivačima teksta
  • Ulančavanje hash tablica za rješavanje sudara
  • Navigacija popisa pjesama za reprodukciju glazbe ili videozapisa
  • Reprezentacija susjednosti grafa
  • Polinomske aritmetičke operacije

Ovi primjeri ističu kako povezane liste pružaju fleksibilnost i učinkovitu manipulaciju nizovima tamo gdje bi promjena veličine niza bila skupa.

12) Objasnite razliku između jednostruko i dvostruko povezane liste.

svojstvo Pojedinačno povezani popis Dvostruko povezana lista
upućuje 1 (samo sljedeći čvor) 2 (prethodni i sljedeći)
obuhvaćanje Samo jedan smjer Oba smjera
Memorija Običaj Less (samo jedan pokazivač) Više (dodatni pokazivač)
brisanje Teže (potreban prethodni čvor) Jednostavnije
Primjer upotrebe Implementacija stoga Navigacija povijesti preglednika

A dvostruko povezana lista je svestraniji, ali troši dodatnu memoriju. Nasuprot tome, pojedinačno povezane liste lagani su i učinkoviti za jednosmjerni prolaz.

13) Kako ukloniti duplikate iz sortirane povezane liste?

Kada je povezana lista već sortirana, duplikati će biti susjedni.

Prođite kroz popis i usporedite podatke svakog čvora sa sljedećim čvorom. Ako se podudaraju, preskočite sljedeći čvor.

void removeDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
}

Složenost: O(n) vremena i O(1) prostora.

Za nesortirane popise, HashSet se može koristiti za praćenje viđenih vrijednosti.

14) Koja je razlika između linearne i kružne povezane liste?

svojstvo Linearna povezana lista Kružni povezani popis
Posljednji čvor Bodovi za NULL Ukazuje na glavni čvor
obuhvaćanje Završava kada next == NULL Neprekidni prolaz
Koristite slučaj Stog, Red čekanja Kružno raspoređivanje
Složenost jednostavnije Složenije rukovanje

Kružne liste su posebno korisne u primjenama kao što je raspoređivanje CPU-a, gdje se procesi ciklički izvršavaju.

15) Kako se pronalazi presjek dviju povezanih lista?

Da biste utvrdili sijeku li se dvije jednostruko povezane liste:

  1. Izračunajte duljine oba popisa.
  2. Pomakni pokazivač dužeg popisa za razliku u duljinama.
  3. Prolazite obje liste istovremeno dok čvorovi ne postanu identični.

Alternativno, a HashSet može se koristiti za pohranjivanje posjećenih čvorova za O(n) prostora.

Ovaj pristup je učinkovit i često se postavlja u intervjuima za rukovodeće pozicije.

16) Kako provjeriti jesu li dvije povezane liste identične?

Dvije povezane liste su identične ako:

  • Imaju isti broj čvorova.
  • Odgovarajuće vrijednosti čvorova su identične po redoslijedu.

Algoritam:

  1. Pregledajte oba popisa zajedno.
  2. Usporedite podatke svakog čvora.
  3. Ako se svi parovi podudaraju i oba dosegnu NULL, identični su.

Vremenska složenost: O (n)

Složenost prostora: O (1)

17) Što je curenje memorije u kontekstu povezanih lista?

A curenje memorije događa se kada dinamički dodijeljeni čvorovi nisu oslobođeni nakon upotrebe.

U povezanim listama, ako delete or free() ne poziva se na čvorovima uklonjenim s popisa, memorija ostaje zauzeta iako više nije dostupna.

Na primjer, neuspjeh u oslobađanju izbrisanih čvorova u C/C++ dovodi do postupnog iscrpljivanja memorije, što uzrokuje usporavanje ili pad sustava.

Pravilno čišćenje pomoću destruktora ili eksplicitne dealokacije izbjegava ovaj problem.

18) Objasnite kako implementirati stog pomoću povezane liste.

U stog, elementi slijede LIFO redoslijed (Last In, First Out - zadnji unutra, prvi van).

Povezana lista je idealna jer se umetanja i brisanja učinkovito događaju na početku.

Operaticije:

  • Gurnuti: Umetnite novi čvor na zaglavlje.
  • Pop: Uklonite čvor s glave.
  • Zaviriti: Vrati podatke o glavi.

Prednosti:
Nema potrebe za nizom fiksne veličine; raste dinamički kako se elementi dodaju.

19) Kako se povezana lista može koristiti za implementaciju reda čekanja?

U red, elementi slijede FIFO (First In, First Out) redoslijed.

Koristite povezanu listu gdje:

  • Umetanje (Dodaj u red): Dodajte čvor na repu.
  • Ukloni (Decomposite Reach): Izbriši čvor iz glave.

To omogućuje obje operacije u O (1) vrijeme s dva pokazivača — front i rear.

Obično se koristi u sustavima za raspoređivanje procesa i redovima čekanja pisača.

20) Koje su razlike između niza popisa i povezanog popisa u Java?

Aspekt ArrayList LinkedList
Čuvanje Dinamički niz Dvostruko povezana lista
Vrijeme pristupa O (1) O (n)
Umetni/Izbriši Skupo u sredini Učinkovito na kraju
Opterećenje memorije Less Više (dodatni savjeti)
Koristite slučaj Česti pristup Često umetanje/brisanje

Primjer: Koristiti ArrayList za operacije s velikim brojem pretraga i LinkedList kada dominiraju operacije umetanja/brisanja.

21) Kako izravnati višerazinsku povezanu listu?

A višerazinska povezana lista može sadržavati čvorove koji imaju oboje next i child pokazivači (svako dijete vodi do druge povezane liste). Cilj je izravnati sve čvorove u povezanu listu jedne razine.

Pristup:

  1. Koristiti stog or rekurzivna funkcija.
  2. Počnite od glavnog čvora.
  3. Ako čvor ima childgurni ga next čvor na stog i napravi child as next.
  4. Nastavite dok se stog ne isprazni.

Složenost vremena: O (n)

Složenost prostora: O(n) za rekurziju/slog.

Primjer (konceptualno):

1 - 2 - 3
    |
    4 - 5
Flattened → 1 → 2 → 4 → 5 → 3

Ovo pitanje procjenjuje vaše razumijevanje rekurzije i manipulacije pokazivačima.

22) Kako klonirati povezanu listu sa slučajnim pokazivačima?

Svaki čvor u ovoj posebno povezanoj listi ima dva pokazivača:

  • next → pokazuje na sljedeći čvor.
  • random → pokazuje na bilo koji proizvoljni čvor.

Algoritam (3 koraka):

  1. Umetnite klonirane čvorove između originalnih čvorova.
  2. Dodijelite slučajne pokazivače za klonove (clone.random = original.random.next).
  3. Odvojite dva popisa.

Time se izbjegava dodatni prostor za hash mapu i izvršava se u O (n) vrijeme sa O (1) dodatni prostor.

Slučaj upotrebe: Dubinsko kopiranje složenih struktura podataka (npr. grafova ili referenci objekata).

23) Što je lista za preskakanje i kako je povezana s povezanim listama?

A popis za preskakanje je slojevita struktura povezanih lista koja omogućuje brzo pretraživanje, umetanje i brisanje (slično uravnoteženim stablima).

OperaANJE Prosječno vrijeme Najgori slučaj
Traži O (zapisnik n) O (n)
Umetni/Izbriši O (zapisnik n) O (n)

Sadrži više razina, gdje gornje razine "preskaču" nekoliko čvorova, poboljšavajući učinkovitost pretraživanja.

Primjer: Koristi se u bazama podataka poput Redisa i istovremenim implementacijama mapa.

24) Kako možete otkriti palindrom u povezanoj listi?

Povezana lista je palindrom ako se čita isto unaprijed i unatrag.

Algoritam:

  1. Pronađite sredinu popisa.
  2. Revprije druge polovice.
  3. Usporedite dvije polovice čvor po čvor.

Ako se svi odgovarajući čvorovi podudaraju, to je palindrom.

Primjer:

1 → 2 → 3 → 2 → 1 → ✅ Palindrom

1 → 2 → 3 → 4 → ❌ Nije palindrom

Složenost vremena: O (n)

Složenost prostora: O (1)

25) Kako ukloniti petlju u povezanoj listi?

Ako postoji petlja (korištenjem Floydovog detektiranja ciklusa), uklonite je slijedeći ove korake:

  1. Otkrijte mjesto susreta sporih i brzih pokazivača.
  2. Pomaknite jedan pokazivač prema glavi.
  3. Pomičite oba pokazivača korak po korak dok se ne sretnu u početni čvor petlje.
  4. Postavi prethodni čvor next do null.

Ovaj pristup osigurava da nema dodatne upotrebe memorije prilikom rješavanja ciklusa.

26) Koji su različiti načini predstavljanja povezanih lista u memoriji?

Povezane liste mogu se predstaviti u tri glavna načina:

Vrsta reprezentacije Description Primjer upotrebe
Dinamički čvorovi Svaki čvor dinamički dodijeljen i povezan C, C++
Statička reprezentacija niza Koristi indekse polja umjesto pokazivača Ugrađeni sustavi
Povezani objekti Objektno orijentirana reprezentacija s klasama Java, Python

Svaki pristup odgovara različitim okruženjima - na primjer, liste temeljene na nizovima koriste se kada je manipulacija pokazivačem ograničena.

27) Kako možete pronaći duljinu povezane liste (iterativne i rekurzivne)?

Iterativni pristup:

int getLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

Rekurzivni pristup:

int getLength(ListNode head) {
    if (head == null) return 0;
    return 1 + getLength(head.next);
}

Oba pristupa imaju O (n) vremenska složenost; rekurzija dodaje O (n) prostor opterećen zbog steka poziva.

28) Objasnite koncept kružnih dvostruko povezanih lista s primjerom.

U kružna dvostruko povezana lista, svaki čvor ima dvije veze - jednu prema sljedećem i jednu prema prethodnom - a posljednjeg čvora next pokazuje na glavu, dok je glava prev ukazuje na posljednji čvor.

Primjeri slučajeva upotrebe:

  • Operativni sustavi u stvarnom vremenu (kružno raspoređivanje)
  • Petlja glazbene playliste
  • Navigacija između kartica ili slajdova

Prednosti:

  • Dvosmjerni obilazak.
  • Nema nultih referenci.
  • Učinkovito umetanje i brisanje.

29) Kako se brišu alternativni čvorovi u povezanoj listi?

Algoritam:

  1. Počnite od glave.
  2. Izbrišite svaki drugi čvor prilagođavanjem pokazivača.
  3. Nastavite dok se popis ne završi.

Primjer:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 3 → 5

Složenost:

  • Vrijeme: O(n)
  • Prostor: O(1)

Ovo provjerava razumijevanje sigurnosti prolaska pokazivača i brisanja.

30) Kako možete pronaći n-ti čvor s početka i s kraja povezane liste?

S početka: Prolazite kroz listu dok broj ne bude = n.

Od kraja: Koristite dva pokazivača.

  1. Pomakni prvi pokazivač n koraka naprijed.
  2. Pomičite oba istovremeno dok prvi ne dosegne nulu.
  3. Drugi pokazivač sada pokazuje na n-ti čvor od kraja.

Složenost vremena: O (n)

Složenost prostora: O (1)

Ovaj pristup izbjegava zasebno izračunavanje duljine, što poboljšava učinkovitost.

31) Kako se mijenja redoslijed povezane liste?

Problem: S obzirom na popis L0 → L1 → … → Ln-1 → Ln, promijenite redoslijed kao L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Koraci:

  1. Pronađite sredinu popisa.
  2. Revprije druge polovice.
  3. Spojite dvije polovice naizmjenično.

Primjer:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 5 → 2 → 4 → 3

Složenost: O(n) vremena, O(1) prostora.

Ovo testira više operacija povezanih lista u jednom pitanju.

32) Kako particionirate povezanu listu oko zadane vrijednosti x?

Cilj:
Preuredi čvorove tako da svi čvorovi manji od x dolaze prije čvorova većih ili jednakih od x.

Pristup:

  • Održavajte dvije lažne liste: before i after.
  • Prođite kroz izvornu listu i dodajte čvorove odgovarajućim listama.
  • Spojite ih na kraju.

Primjer:

Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5  
Output: 3 → 2 → 1 → 5 → 8 → 5 → 10

Ovo se često traži za procjenu sposobnosti preuređenja podataka.

33) Kako sortirate povezanu listu?

Budući da povezane liste ne podržavaju slučajni pristup, Spoji sortiranje je najbolji izbor.

Koraci:

  1. Podijelite popis na polovice koristeći spore/brze pokazivače.
  2. Rekurzivno sortiraj svaku polovicu.
  3. Spoji sortirane polovice.

Prednosti:

  • O(n log n) vremena.
  • O(1) dodatnog prostora (za iterativnu verziju).

Za razliku od nizova, QuickSort je neučinkovit za povezane liste zbog složenosti preuređenja pokazivača.

34) Koja je razlika između jednostruko, dvostruko i kružno povezanih lista?

svojstvo Pojedinačno Dvostruko Kružni
linkovi Jedan (sljedeći) Dva (prethodna i sljedeća) Posljednji čvor spaja se s glavom
obuhvaćanje Samo naprijed Naprijed i nazad Moguće beskonačno kretanje
Umetanje/brisanje Umjereno Lakše s obje strane Obrada posebnih slučajeva
Koristite slučaj Stog, Red čekanja Poništi operacije Kružno raspoređivanje

Ovo pitanje usporedbe često se čini kao provjera konceptualne jasnoće.

35) Kako se pronalazi presjek dviju kružnih povezanih lista?

Ovo je proširenje problema raskrižja.

Algoritam:

  1. Otkrij ima li svaka lista petlju.
  2. Ako su oba aciklička → koristite standardni algoritam presjeka.
  3. Ako su oba ciklička → pronađite početak petlje za svaku i provjerite jesu li isti ili povezani.

Ovaj problem kombinira detekcija ciklusa i logika presjeka, testiranje višekonceptualnog zaključivanja.

36) Objasnite kako umetnuti čvor u sortiranu povezanu listu.

Koraci:

  1. Stvorite novi čvor s danom vrijednošću.
  2. Pomičite se dok ne pronađete ispravan položaj.
  3. prilagoditi next pokazivače u skladu s tim.

Primjer:

Input: 1 → 3 → 5 → 7, Insert 4  
Output: 1 → 3 → 4 → 5 → 7

Ovo je osnovni manipulacijski problem za testiranje razumijevanja podešavanja pokazivača.

37) Kako podijeliti povezanu listu na dvije polovice?

Algoritam:

  • Koristite metodu sporog i brzog pokazivača.
  • Prilikom fast dođe do kraja, slow bit će na sredini.
  • Podijeli se na tom čvoru.

Primjer:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 2 → 3  and  4 → 5

Ova operacija je često prvi korak sortiranja spajanjem povezanih lista.

38) Kako pronaći posljednju pojavu vrijednosti u povezanoj listi?

Krećite se kroz popis prateći posljednji čvor u kojem se nalazi ciljna vrijednost.

Pseudokod:

ListNode findLastOccurrence(ListNode head, int val) {
    ListNode result = null;
    while (head != null) {
        if (head.val == val) result = head;
        head = head.next;
    }
    return result;
}

Složenost: O (n)

Ovo provjerava razumijevanje linearnog obilaska i provjere uvjeta.

39) Kako možete ukloniti sva pojavljivanja zadanog ključa iz povezane liste?

Algoritam:

  1. Prvo obradi glavne čvorove ako sadrže ciljni ključ.
  2. Zatim prođite kroz i izbrišite sljedeće čvorove koji sadrže ključ.

Primjer:

Input: 1 → 2 → 6 → 3 → 4 → 5 → 6, Key = 6  
Output: 1 → 2 → 3 → 4 → 5

Složenost: O (n)

Ovo pokazuje poznavanje rubnih slučajeva (posebno brisanja glava).

40) Koje su ključne razlike između podatkovnih struktura stoga i povezanih popisa?

svojstvo Stog Povezani popis
Vrsta pristupa LIFO (zadnji ušao, prvi izašao) Sekvencijalno
Izvršenje Niz ili povezana lista Temeljeno na čvorovima
Operama Guranje/Popucavanje Umetni/Izbriši/Pomakni
Fleksibilnost Ograničeni pristup Fleksibilan pristup
Koristite slučaj Upravljanje pozivima funkcija Dinamičko rukovanje podacima

Stog se može implementirati korištenjem povezane liste, ali se razlikuju po konceptu - stog ima ograničen pristup, dok je povezana lista struktura opće namjene.

🔍 Popis najpopularnijih pitanja za intervju s realnim scenarijima i strateškim odgovorima

1) Što je povezana lista i po čemu se razlikuje od niza?

Očekivano od kandidata: Anketar želi procijeniti vaše razumijevanje osnovnih struktura podataka i vašu sposobnost uspoređivanja kompromisa.

Primjer odgovora: Povezana lista je linearna struktura podataka u kojoj su elementi, nazvani čvorovi, povezani pokazivačima. Svaki čvor sadrži podatke i referencu na sljedeći čvor. Za razliku od nizova, povezane liste ne zahtijevaju susjednu memoriju i omogućuju dinamičku promjenu veličine, ali imaju sporije vrijeme pristupa jer elementi nisu indeksirani.

2) Kada biste u stvarnoj primjeni odabrali povezanu listu umjesto niza?

Očekivano od kandidata: Oni procjenjuju vašu praktičnu prosudbu u odabiru odgovarajućih struktura podataka.

Primjer odgovora: Odabrao bih povezanu listu kada su potrebna česta umetanja i brisanja, posebno u sredini skupa podataka. U prethodnoj ulozi radio sam na značajki raspoređivanja zadataka gdje su se zadaci često dodavali i uklanjali, a povezana lista pružala je bolje performanse od polja.

3) Možete li objasniti razliku između jednostruko povezanih i dvostruko povezanih lista?

Očekivano od kandidata: Ispitivač želi provjeriti vašu konceptualnu jasnoću i sposobnost jasnog objašnjavanja tehničkih razlika.

Primjer odgovora: Jednostruko povezana lista ima čvorove koji pokazuju samo na sljedeći čvor, dok dvostruko povezana lista ima čvorove koji pokazuju i na sljedeći i na prethodni čvor. Dvostruko povezane liste omogućuju lakše kretanje unatrag, ali zahtijevaju više memorije zbog dodatnog pokazivača.

4) Kako biste otkrili ciklus u povezanoj listi?

Očekivano od kandidata: Ovo testira vaše vještine rješavanja problema i poznavanje uobičajenih algoritamskih obrazaca.

Primjer odgovora: Uobičajeni pristup je korištenje dvaju pokazivača koji se kreću različitim brzinama, često nazvan tehnikom sporog i brzog pokazivača. Ako postoji ciklus, dva pokazivača će se na kraju susresti. Na prethodnoj poziciji koristio sam ovaj pristup kako bih spriječio beskonačne petlje u cjevovodu obrade podataka.

5) Koje se uobičajene operacije izvode na povezanim listama?

Očekivano od kandidata: Anketar želi vidjeti razumijete li standardne operacije i njihove implikacije.

Primjer odgovora: Uobičajene operacije uključuju umetanje, brisanje, prolazak kroz popis, pretraživanje i preokretanje. Svaka operacija ima različitu vremensku složenost ovisno o tome gdje se izvodi, što je važno pri dizajniranju učinkovitih sustava.

6) Kako se rješava umetanje čvora u sredinu povezane liste?

Očekivano od kandidata: Provjeravaju vaše razumijevanje manipulacije pokazivačem i pažnju prema detaljima.

Primjer odgovora: Za umetanje čvora u sredinu, prvo se krećem kroz popis kako bih pronašao ciljni položaj, a zatim prilagođavam pokazivače tako da novi čvor pokazuje na sljedeći čvor, a prethodni čvor na novi čvor. Pažljivo ažuriranje pokazivača ključno je kako bi se izbjeglo narušavanje popisa.

7) Opišite situaciju u kojoj je povezana lista uzrokovala probleme s performansama i kako ste je riješili.

Očekivano od kandidata: Ovo bihevioralno pitanje procjenjuje vašu sposobnost promišljanja i optimizacije.

Primjer odgovora: Na mom prethodnom poslu, povezana lista se koristila za česte operacije pretraživanja, što je dovodilo do sporih performansi. Utvrdio sam problem i preporučio prelazak na strukturu temeljenu na hash-u, što značajno poboljšava vrijeme pretraživanja.

8) Kako biste preokrenuli povezanu listu?

Očekivano od kandidata: Ispitivač provjerava vaše logičko razmišljanje i razumijevanje iterativnih ili rekurzivnih pristupa.

Primjer odgovora: Povezanu listu bih preokrenuo iteracijom kroz nju i promjenom sljedećeg pokazivača svakog čvora da pokazuje na prethodni čvor. Ovaj se proces nastavlja sve dok se svi pokazivači ne preokrenu i zaglavlje ne ažurira.

9) Koje su prednosti i nedostaci korištenja povezanih popisa?

Očekivano od kandidata: Žele uravnoteženu perspektivu i svijest o kompromisima.

Primjer odgovora: Prednosti uključuju dinamičku veličinu i učinkovito umetanje i brisanje. Nedostaci uključuju veću upotrebu memorije i sporije vrijeme pristupa u usporedbi s nizovima. U mojoj posljednjoj ulozi, razumijevanje ovih kompromisa pomoglo je u odabiru prave strukture za različite komponente.

10) Kako odlučujete koju vrstu povezane liste koristiti u dizajnu sustava?

Očekivano od kandidata: Ovo situacijsko pitanje procjenjuje donošenje odluka u arhitektonskim kontekstima.

Primjer odgovora: Uzimam u obzir čimbenike kao što su potrebe za prolaskom kroz popis, memorijska ograničenja i učestalost operacija. Na primjer, ako je potreban prolazak unatrag, dvostruko povezana lista je prikladnija, dok je jednostruko povezana lista dovoljna za jednostavnije, memorijski učinkovite implementacije.

Sažmite ovu objavu uz: