Top 40 interviewvragen en -antwoorden over Linked Lists (2026)
Sara Chen
Voorbereiding op een interview over datastructuren vereist focus op uitdagingen. Interviewvragen over gekoppelde lijsten onthullen de diepgang van probleemoplossend vermogen, pointerlogica, geheugenbewustzijn en hoe kandidaten redeneren in uitzonderlijke gevallen.
Het beheersen van linked lists opent deuren naar functies binnen productteams, platformen en systeemontwikkeling. Praktische ervaring bouwt sterke technische expertise, analytisch denkvermogen en schone codeergewoonten op. Van starters tot senior professionals, deze vaardigheden ondersteunen daadwerkelijk debuggen, prestatieanalyses uitvoeren, juniors begeleiden en samenwerken met managers aan schaalbare oplossingen met behulp van geavanceerde concepten uit de praktijk. Lees meer ...
👉 Gratis PDF-download: Interviewvragen en -antwoorden over linked lists
Top Linked List Interviewvragen en -antwoorden
1) Leg uit wat een gekoppelde lijst is en hoe deze verschilt van een array.
A gekoppelde lijst Een linked list is een lineaire datastructuur waarbij elementen, knooppunten genaamd, met elkaar verbonden zijn door middel van pointers of referenties. Elk knooppunt bevat gegevens en een pointer/referentie naar het volgende knooppunt in de lijst. In tegenstelling tot arrays slaan linked lists elementen niet op in aaneengesloten geheugen.
Belangrijkste verschillen tussen een gekoppelde lijst en een array:
| Kenmerk | Gelinkte lijst | reeks |
|---|---|---|
| Geheugentoewijzing | Dynamisch | Statisch |
| Toegangstijd tot elementen | O (n) | O (1) |
| Invoegen/verwijderen | Efficiënt (in elke functie) | Kostbaar (moet verplaatst worden) |
| Geheugenoverhead | Extra ruimte voor aanwijzers | Geen extra overhead voor aanwijzers |
Samenvattend bieden gekoppelde lijsten een afweging tussen snellere invoegingen en dynamische grootteaanpassing, maar wel met een tragere willekeurige toegang en extra geheugenoverhead als gevolg van pointers.
2) Wat zijn de verschillende soorten gekoppelde lijsten?
Er zijn verschillende soorten gekoppelde lijstenEn interviewers vragen je vaak om onderscheid te maken tussen deze twee:
- Enkelvoudig gekoppelde lijst: Elk knooppunt wijst alleen naar het volgende knooppunt.
- Dubbel gekoppelde lijst: Knooppunten hebben twee aanwijzers: één naar het volgende en één naar het vorige knooppunt.
- Circulaire gekoppelde lijst: Het laatste knooppunt wijst terug naar het eerste knooppunt, waardoor een lus ontstaat.
- Dubbel circulaire gekoppelde lijst: Combineert zowel circulaire als dubbel gekoppelde lijsten.
Elk type heeft verschillende toepassingsmogelijkheden, afhankelijk van de benodigde doorlooptijd en het geheugenverbruik. Dubbelgelinkte lijsten maken bijvoorbeeld een gemakkelijke achterwaartse doorloop mogelijk, ten koste van extra pointers.
3) Hoe keer je een enkelvoudig gekoppelde lijst om? (Programmeeraanpak)
RevHet omkeren van een gelinkte lijst is een klassieke interviewvraag. Het doel is om de richting van de pointers te veranderen, zodat de lijst op zijn plaats wordt omgekeerd zonder nieuwe knooppunten aan te maken.
Kernidee:
Gebruik drie aanwijzers — prev, curren next — en doorloop de lijst. Leid bij elke stap door. curr.next naar prev, en schuif vervolgens alle pointers door.
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
}
Dit transformeert de gekoppelde structuur zonder extra ruimte en loopt in O (n) tijd.
4) Leg de tweepuntsmethode uit om het midden van een gekoppelde lijst te vinden.
De meest efficiënte manier om het middelste knooppunt van een gekoppelde lijst te vinden, is door twee pointers te gebruiken:
- A trage aanwijzer verplaatst één knooppunt tegelijk.
- A snelle aanwijzer verplaatst twee knooppunten tegelijk.
Wanneer de snelle aanwijzer het einde bereikt, bevindt de langzame aanwijzer zich in het midden. Deze techniek werkt in O (n) tijd zonder extra ruimte.
5) Hoe zou je een cyclus in een gekoppelde lijst detecteren?
Cyclusdetectie is een ander klassiek probleem. De standaardoplossing maakt gebruik van Floyds schildpad-en-haas-algoritme:
- Verplaatsen
slow pointerstap voor stap. - Verplaatsen
fast pointertwee stappen tegelijk. - Als de lijst een cyclus bevat, zullen de twee pointers elkaar kruisen.
Als de snelle aanwijzer het volgende bereikt: nullDe lijst bevat geen cycli. Deze methode werkt in O (n) tijd en O (1) ruimte.
6) Wat zijn de voor- en nadelen van gekoppelde lijsten?
Gekoppelde lijsten bieden verschillende voordelen en nadelen:
| Voordelen | Nadelen |
|---|---|
| Dynamische grootte | Geen willekeurige toegang |
| Eenvoudig invoegen/verwijderen | Extra geheugen voor pointers |
| Efficiënt voor groeiende datasets | Slechte cacheprestaties |
Gekoppelde lijsten presteren goed bij dynamische data, maar kunnen trager zijn dan arrays voor elementtoegang, omdat elke toegang vanaf het begin van de lijst moet worden doorlopen.
7) Hoe voeg je twee gesorteerde gekoppelde lijsten samen?
Het samenvoegen van twee gesorteerde lijsten is een andere veelvoorkomende interviewopgave. Het idee is om beide lijsten gelijktijdig te doorlopen en een nieuwe gesorteerde lijst te maken door bij elke stap het kleinste knooppunt uit een van beide lijsten te selecteren.
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;
}
Deze methode behoudt de sorteervolgorde en werkt in O(n + m) tijd voor lijsten van lengte n en m.
8) Leg uit hoe je het N-de knooppunt aan het einde van een gekoppelde lijst verwijdert.
De meest efficiënte techniek maakt gebruik van twee aanwijzers Gescheiden door n knooppunten. Verplaats de eerste aanwijzer n stappen, verplaats vervolgens beide aanwijzers totdat de eerste het einde bereikt. De tweede aanwijzer bevindt zich dan net voor het doelknooppunt.
Dit voorkomt dat de lengte van de lijst apart berekend hoeft te worden en voltooit de berekening in O (n) tijd. Het behandelt ook uitzonderlijke gevallen, zoals het verwijderen van het eerste knooppunt.
9) Wat is de tijdscomplexiteit om het k-de element in een gekoppelde lijst te benaderen?
Toegang tot de kHet i-de element in een gekoppelde lijst vereist een doorloop vanaf het begin tot het einde. khet e knooppunt. Omdat gekoppelde lijsten geen directe indexering bieden, kost dit geld. O (n) tijd in het ergste geval.
Daarentegen ondersteunen arrays directe indexering in O (1) tijd.
10) Waarom zou je een gekoppelde lijst gebruiken in plaats van een array?
Gekoppelde lijsten zijn vooral handig wanneer:
- Je verwacht frequente invoegingen en verwijderingen op willekeurige posities.
- Je weet de omvang van je gegevens niet van tevoren.
- Geheugenfragmentatie maakt het lastig om aaneengesloten geheugen toe te wijzen.
Ze ondersteunen efficiënte dynamische geheugenallocatie en invoegen/verwijderen in constante tijd aan het einde van lijsten of met een bekende knooppuntreferentie – voordelen die arrays niet kunnen evenaren.
11) Wat zijn de praktische toepassingen van gekoppelde lijsten?
Gekoppelde lijsten worden veel gebruikt in systemen waar dynamische geheugentoewijzing, frequente invoegingenof datastructuren met variabele grootte zijn vereist. Ze worden geïmplementeerd in verschillende kernconcepten en -toepassingen binnen de informatica, zoals:
- Dynamisch geheugenbeheer (gebruikt in besturingssystemen)
- Functies voor ongedaan maken/opnieuw uitvoeren in tekstverwerkers
- Hash-tabelkoppeling om botsingen op te lossen
- Navigatie door muziek- of video-afspeellijsten
- Grafiekaangrenzendheidsrepresentatie
- Polynoom rekenkundige bewerkingen
Deze voorbeelden laten zien hoe gekoppelde lijsten flexibiliteit en efficiënte manipulatie van sequenties mogelijk maken, waar het aanpassen van de grootte van een array kostbaar zou zijn.
12) Leg het verschil uit tussen een enkelvoudig en een dubbelvoudig gekoppelde lijst.
| Kenmerk | Afzonderlijk gekoppelde lijst | Dubbel gelinkte lijst |
|---|---|---|
| Pointers | 1 (alleen volgende knooppunt) | 2 (vorige en volgende) |
| traversal | Slechts één richting | Beide richtingen |
| Geheugengebruik | Less (slechts één aanwijzer) | Meer (extra aanwijzer) |
| Recht op verwijdering | Moeilijker (vorige knooppunt nodig) | Gemakkelijker |
| Voorbeeld gebruik | Stack-implementatie | Browsergeschiedenisnavigatie |
A dubbel gekoppelde lijst is veelzijdiger, maar verbruikt meer geheugen. Daarentegen, enkelvoudig gelinkte lijsten Ze zijn licht van gewicht en efficiënt voor eenrichtingsverkeer.
13) Hoe verwijder je duplicaten uit een gesorteerde gekoppelde lijst?
Als een gekoppelde lijst al gesorteerd is, staan duplicaten naast elkaar.
Doorloop de lijst en vergelijk de gegevens van elk knooppunt met die van het volgende knooppunt. Als ze overeenkomen, sla dan het volgende knooppunt over.
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;
}
}
}
complexiteit: O(n) tijd en O(1) ruimte.
Voor ongesorteerde lijsten kan een HashSet worden gebruikt om bij te houden welke waarden al zijn gezien.
14) Wat is het verschil tussen een lineaire en een circulaire gekoppelde lijst?
| Kenmerk | Lineaire gekoppelde lijst | Circulaire gekoppelde lijst |
|---|---|---|
| Laatste knooppunt | Wijst naar NULL | Wijst naar het hoofdknooppunt |
| traversal | Eindigt wanneer next == NULL |
Continue doorloop |
| Use Case | Stapel, wachtrij | Round-robin-planning |
| Ingewikkeldheid | eenvoudiger | Complexere afhandeling |
Circulaire lijsten zijn met name nuttig in toepassingen zoals CPU-planning, waarbij processen cyclisch worden uitgevoerd.
15) Hoe vind je het snijpunt van twee gekoppelde lijsten?
Om te bepalen of twee enkelvoudig gekoppelde lijsten elkaar overlappen:
- Bepaal de lengte van beide lijsten.
- Schuif de aanwijzer van de langere lijst op met het verschil in lengte.
- Doorloop beide lijsten gelijktijdig totdat de knooppunten identiek zijn.
Als alternatief kan een HashSet kan worden gebruikt om bezochte knooppunten op te slaan met een geheugenbehoefte van O(n).
Deze aanpak is efficiënt en wordt vaak gevraagd tijdens sollicitatiegesprekken voor hogere functies.
16) Hoe controleer je of twee gekoppelde lijsten identiek zijn?
Twee gekoppelde lijsten zijn identiek als:
- Ze hebben hetzelfde aantal knooppunten.
- De corresponderende knooppuntwaarden zijn in dezelfde volgorde.
Algoritme:
- Doorloop beide lijsten tegelijk.
- Vergelijk de gegevens van elk knooppunt.
- Als alle paren overeenkomen en beide NULL opleveren, zijn ze identiek.
Tijdcomplexiteit: O (n)
Ruimtecomplexiteit: O (1)
17) Wat is een geheugenlek in de context van gekoppelde lijsten?
A geheugenlek Dit gebeurt wanneer dynamisch toegewezen knooppunten na gebruik niet worden vrijgegeven.
In gekoppelde lijsten, als delete or free() De functie wordt niet aangeroepen voor knooppunten die uit de lijst zijn verwijderd; het geheugen blijft bezet, ook al is het niet langer toegankelijk.
Bijvoorbeeld, het niet vrijgeven van verwijderde knooppunten in C/C++ Dit leidt tot geleidelijke geheugenuitputting, waardoor het systeem trager wordt of vastloopt.
Een correcte opruiming met behulp van een destructor of expliciete deallocatie voorkomt dit probleem.
18) Leg uit hoe je een stack implementeert met behulp van een linked list.
In een stackDe elementen worden volgens het LIFO-principe (Last In, First Out) verwerkt.
Een gekoppelde lijst is ideaal omdat invoegingen en verwijderingen efficiënt aan het begin plaatsvinden.
Operabanden:
- Push: Voeg een nieuw knooppunt toe aan het begin.
- Knal: Verwijder het knooppunt uit de header.
- Kijkje: Retourneer kopgegevens.
Voordelen:
Een array met een vaste grootte is niet nodig; deze groeit dynamisch naarmate er elementen aan worden toegevoegd.
19) Hoe kan een gekoppelde lijst worden gebruikt om een wachtrij te implementeren?
In een queueDe elementen worden volgens het FIFO-principe (First In, First Out) verwerkt.
Gebruik een gekoppelde lijst wanneer:
- In de wachtrij plaatsen (Invoegen): Voeg een knooppunt toe aan het einde.
- Verwijderen uit de wachtrij: Verwijder het knooppunt uit de header.
Dit maakt beide bewerkingen mogelijk in O (1) tijd met twee aanwijzers — front en rear.
Het wordt veel gebruikt in procesplannings- en printerwachtrijsystemen.
20) Wat zijn de verschillen tussen een arraylist en een linkedlist? Java?
| Aspect | ArrayLijst | Gekoppelde lijst |
|---|---|---|
| Opslag | Dynamische array | Dubbel gekoppelde lijst |
| Toegangstijd | O (1) | O (n) |
| Invoegen/Verwijderen | Duur in het midden. | Efficiënt aan het einde |
| Geheugenoverhead | Less | Meer (extra tips) |
| Use Case | Regelmatige toegang | Frequente invoeging/verwijdering |
Voorbeeld: Gebruik ArrayList voor bewerkingen die veel zoekopdrachten vereisen, en LinkedList wanneer invoeg-/verwijderingsbewerkingen de overhand hebben.
21) Hoe maak je een gelinkte lijst met meerdere niveaus plat?
A meerlaagse gekoppelde lijst kan knooppunten bevatten die beide hebben next en child pointers (waarbij elk kind naar een andere gekoppelde lijst leidt). Het doel is om alle knooppunten samen te voegen tot een gekoppelde lijst met één niveau.
Nadering:
- Gebruik een stack or recursieve functie.
- Begin bij het hoofdknooppunt.
- Als een knooppunt een
childduwt zijnnextnode aan de stack toevoegen en makenchildasnext. - Ga door tot de stapel leeg is.
Tijdscomplexiteit: O (n)
Ruimtecomplexiteit: O(n) voor recursie/stack.
Voorbeeld (conceptueel):
1 - 2 - 3
|
4 - 5
Flattened → 1 → 2 → 4 → 5 → 3
Deze vraag toetst uw begrip van recursie en pointermanipulatie.
22) Hoe kloon je een gekoppelde lijst met willekeurige pointers?
Elk knooppunt in deze speciale gekoppelde lijst heeft twee pointers:
next→ wijst naar het volgende knooppunt.random→ wijst naar een willekeurig knooppunt.
Algoritme (3 stappen):
- Voeg gekloonde knooppunten in tussen de originele knooppunten.
- Wijs willekeurige pointers toe aan klonen (
clone.random = original.random.next). - Scheid de twee lijsten.
Dit voorkomt extra ruimte voor een hashmap en werkt in O (n) tijd met O (1) extra ruimte.
Use case: Diep kopiëren van complexe datastructuren (bijv. grafieken of objectverwijzingen).
23) Wat is een skiplijst en hoe is deze gerelateerd aan gekoppelde lijsten?
A lijst overslaan is een gelaagde gekoppelde lijststructuur die snel zoeken, invoegen en verwijderen mogelijk maakt (vergelijkbaar met gebalanceerde bomen).
| Werking | Gemiddelde tijd | Het slechtste geval |
|---|---|---|
| Zoeken | O (log n) | O (n) |
| Invoegen/Verwijderen | O (log n) | O (n) |
Het bestaat uit meerdere niveaus, waarbij hogere niveaus een aantal knooppunten overslaan, waardoor de zoekefficiëntie wordt verbeterd.
Voorbeeld: Wordt gebruikt in databases zoals Redis en in implementaties van gelijktijdige kaartbewerkingen.
24) Hoe kun je een palindroom in een gekoppelde lijst detecteren?
Een gekoppelde lijst is een palindroom als hij van voor naar achter en van achter naar voor hetzelfde leest.
Algoritme:
- Zoek het midden van de lijst.
- Reverse de tweede helft.
- Vergelijk de twee helften knooppunt voor knooppunt.
Als alle overeenkomende knooppunten overeenkomen, is het een palindroom.
Voorbeeld:
1 → 2 → 3 → 2 → 1 → ✅ Palindroom
1 → 2 → 3 → 4 → ❌ Geen palindroom
Tijdscomplexiteit: O (n)
Ruimtecomplexiteit: O (1)
25) Hoe verwijder je de lus in een gekoppelde lijst?
Als er een lus aanwezig is (volgens Floyds cyclusdetectie), verwijder deze dan met behulp van deze stappen:
- Bepaal het snijpunt van langzame en snelle aanwijzers.
- Verplaats één aanwijzer naar het hoofd.
- Verplaats beide aanwijzers stap voor stap totdat ze elkaar ontmoeten. lus startknooppunt.
- Stel de vorige knooppunt in
nextnaarnull.
Deze aanpak zorgt ervoor dat er geen extra geheugen wordt gebruikt tijdens het oplossen van cycli.
26) Op welke verschillende manieren kunnen gekoppelde lijsten in het geheugen worden weergegeven?
Gekoppelde lijsten kunnen worden weergegeven in drie belangrijke manieren:
| Representatietype | Beschrijving | Voorbeeld gebruik |
|---|---|---|
| Dynamische knooppunten | Elk knooppunt wordt dynamisch toegewezen en gekoppeld. | C, C++ |
| Statische array-representatie | Gebruikt array-indexen in plaats van pointers. | Ingebouwde systemen |
| Gekoppelde objecten | Objectgeoriënteerde representatie met klassen | Java, Python |
Elke aanpak is geschikt voor verschillende omgevingen; zo worden bijvoorbeeld array-gebaseerde lijsten gebruikt wanneer manipulatie van pointers beperkt is.
27) Hoe kun je de lengte van een gekoppelde lijst vinden (iteratief en recursief)?
Iteratieve benadering:
int getLength(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
Recursieve aanpak:
int getLength(ListNode head) {
if (head == null) return 0;
return 1 + getLength(head.next);
}
Beide benaderingen hebben O (n) tijdcomplexiteit; recursie voegt toe O (n) De extra ruimte die nodig is voor de oproepstapel.
28) Leg het concept van circulaire dubbelgelinkte lijsten uit aan de hand van een voorbeeld.
In een circulaire dubbel gekoppelde lijstElk knooppunt heeft twee verbindingen: één naar het volgende en één naar het vorige, en het laatste knooppunt... next wijst naar het hoofd, terwijl het hoofd prev wijst naar het laatste knooppunt.
Voorbeelden van gebruiksscenario's:
- Realtime besturingssystemen (round-robin scheduling)
- Muziek afspeellijst die in een lus wordt afgespeeld
- Navigatie tussen tabbladen of dia's
Voordelen:
- Bidirectionele doorloop.
- Geen null-referenties.
- Efficiënte invoegingen en verwijderingen.
29) Hoe verwijder je afwisselende knooppunten in een gekoppelde lijst?
Algoritme:
- Begin bij het hoofd.
- Verwijder elke tweede knoop door de pointers aan te passen.
- Ga door tot de lijst is afgelopen.
Voorbeeld:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 3 → 5
complexiteit:
- Tijd: O(n)
- Ruimte: O(1)
Dit controleert het begrip van pointer-traversal en de veiligheid van verwijderingen.
30) Hoe vind je het n-de knooppunt vanaf het begin en vanaf het einde van een gekoppelde lijst?
Vanaf het begin: Doorloop de lijst totdat count = n.
Vanaf het einde: Gebruik twee aanwijzers.
- Verplaats de eerste aanwijzer n stappen vooruit.
- Verplaats ze allebei tegelijk totdat de eerste nul bereikt.
- De tweede aanwijzer wijst nu naar het n-de knooppunt vanaf het einde.
Tijdscomplexiteit: O (n)
Ruimtecomplexiteit: O (1)
Deze aanpak voorkomt dat de lengte afzonderlijk berekend hoeft te worden, wat de efficiëntie verbetert.
31) Hoe herschik je een gekoppelde lijst?
Het probleem: Gegeven een lijst L0 → L1 → … → Ln-1 → Ln, herschik het als L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
Stappen:
- Zoek het midden van de lijst.
- Reverse de tweede helft.
- Voeg de twee helften afwisselend samen.
Voorbeeld:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 5 → 2 → 4 → 3
complexiteit: O(n) tijd, O(1) ruimte.
Deze vraag test meerdere gekoppelde lijstbewerkingen.
32) Hoe partitioneer je een gekoppelde lijst rond een gegeven waarde x?
Doel:
Herschik de knooppunten zodanig dat alle knooppunten kleiner dan x vóór de knooppunten groter dan of gelijk aan x komen.
Nadering:
- Houd twee dummylijsten bij:
beforeenafter. - Doorloop de oorspronkelijke lijst en voeg de knooppunten toe aan de respectievelijke lijsten.
- Combineer ze aan het einde.
Voorbeeld:
Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5 Output: 3 → 2 → 1 → 5 → 8 → 5 → 10
Deze vraag wordt vaak gesteld om het vermogen tot gegevensherschikking te evalueren.
33) Hoe sorteer je een gekoppelde lijst?
Aangezien gekoppelde lijsten geen willekeurige toegang ondersteunen, Sorteren samenvoegen is de beste keuze.
Stappen:
- Deel de lijst in tweeën met behulp van langzame/snelle pointers.
- Sorteer elke helft recursief.
- Voeg de gesorteerde helften samen.
Voordelen:
- O(n log n) tijd.
- O(1) extra ruimte (voor de iteratieve versie).
In tegenstelling tot arrays is QuickSort inefficiënt voor gekoppelde lijsten vanwege de complexiteit van de herschikking van pointers.
34) Wat is het verschil tussen enkelvoudig, dubbelvoudig en circulair gekoppelde lijsten?
| Kenmerk | Afzonderlijk | Dubbel | Circulair |
|---|---|---|---|
| Links | Een (volgende) | Twee (vorige & volgende) | Het laatste knooppunt is verbonden met het begin. |
| traversal | Alleen doorsturen | Vooruit en achteruit | Oneindig veel doorloop mogelijk |
| Invoegen/verwijderen | Gemiddeld | Aan beide uiteinden gemakkelijker | Speciale gevalbehandeling |
| Use Case | Stapel, wachtrij | Ongedaan maken-bewerkingen | Round-robin-planning |
Deze vergelijkingsvraag lijkt vaak bedoeld om de conceptuele duidelijkheid te toetsen.
35) Hoe vind je het snijpunt van twee circulaire gekoppelde lijsten?
Dit is een uitbreiding van het snijpuntprobleem.
Algoritme:
- Controleer of elke lijst een lus bevat.
- Als beide acyclisch zijn, gebruik dan het standaard intersectie-algoritme.
- Als beide cyclisch zijn, zoek dan voor elk het beginpunt van de lus en controleer of ze hetzelfde zijn of met elkaar verbonden.
Dit probleem combineert cyclusdetectie en kruispuntlogica, waarbij redeneren met meerdere concepten wordt getest.
36) Leg uit hoe je een knooppunt in een gesorteerde gekoppelde lijst invoegt.
Stappen:
- Maak een nieuw knooppunt aan met de opgegeven waarde.
- Loop verder tot je de juiste positie vindt.
- Adjust
nextdienovereenkomstig aanwijzers.
Voorbeeld:
Input: 1 → 3 → 5 → 7, Insert 4 Output: 1 → 3 → 4 → 5 → 7
Dit is een eenvoudig manipulatieprobleem om het begrip van aanwijzeraanpassing te testen.
37) Hoe splits je een gekoppelde lijst in twee helften?
Algoritme:
- Gebruik de langzame en snelle pointermethode.
- .
fastbereikt het einde,slowzal zich in het midden bevinden. - Splitsen bij dat knooppunt.
Voorbeeld:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 2 → 3 and 4 → 5
Deze bewerking is vaak de eerste stap bij het samenvoegen en sorteren van gekoppelde lijsten.
38) Hoe vind je de laatste keer dat een waarde voorkomt in een gekoppelde lijst?
Doorloop de lijst en houd bij wanneer de gewenste waarde voor het laatst is gevonden.
Pseudocode:
ListNode findLastOccurrence(ListNode head, int val) {
ListNode result = null;
while (head != null) {
if (head.val == val) result = head;
head = head.next;
}
return result;
}
complexiteit: O (n)
Dit toetst het begrip van lineaire doorloop en voorwaardelijke controle.
39) Hoe kun je alle voorkomende instanties van een bepaalde sleutel uit een gekoppelde lijst verwijderen?
Algoritme:
- Behandel eerst de hoofdknooppunten als deze de doelsleutel bevatten.
- Doorloop vervolgens de volgende knooppunten die de sleutel bevatten en verwijder deze.
Voorbeeld:
Input: 1 → 2 → 6 → 3 → 4 → 5 → 6, Key = 6 Output: 1 → 2 → 3 → 4 → 5
complexiteit: O (n)
Dit toont aan dat men kennis heeft van randgevallen (met name kopverwijderingen).
40) Wat zijn de belangrijkste verschillen tussen de datastructuren stack en linked list?
| Kenmerk | Opstapelen | Gelinkte lijst |
|---|---|---|
| Toegangstype | LIFO (Laatst In, Eerst Uit) | Sequential |
| Implementatie | Array of gekoppelde lijst | Op knooppunten gebaseerd |
| Duwen/Pop | Invoegen/Verwijderen/Doorlopen | |
| Flexibiliteit | Beperkte toegang | Flexibele toegang |
| Use Case | Functieaanroepbeheer | Dynamische gegevensverwerking |
Een stapel kan worden geïmplementeerd een gekoppelde lijst gebruikenMaar ze verschillen in concept: een stack heeft beperkte toegang, terwijl een linked list een algemene structuur is.
🔍 Top Linked List interviewvragen met praktijkvoorbeelden en strategische antwoorden
1) Wat is een gekoppelde lijst en waarin verschilt deze van een array?
Verwacht van kandidaat: De interviewer wil uw begrip van fundamentele datastructuren en uw vermogen om afwegingen te maken, beoordelen.
Voorbeeld antwoord: Een gekoppelde lijst is een lineaire datastructuur waarbij elementen, knooppunten genaamd, met elkaar verbonden zijn door middel van pointers. Elk knooppunt bevat gegevens en een verwijzing naar het volgende knooppunt. In tegenstelling tot arrays vereisen gekoppelde lijsten geen aaneengesloten geheugen en maken ze dynamische aanpassing van de grootte mogelijk, maar ze hebben tragere toegangstijden omdat elementen niet geïndexeerd zijn.
2) Wanneer zou je in een praktijktoepassing een gekoppelde lijst boven een array verkiezen?
Verwacht van kandidaat: Ze beoordelen uw praktische oordeel bij het selecteren van geschikte datastructuren.
Voorbeeld antwoord: Ik zou voor een gekoppelde lijst kiezen wanneer er frequent elementen moeten worden toegevoegd en verwijderd, vooral in het midden van de dataset. In mijn vorige functie werkte ik aan een taakplanningsfunctie waarbij taken vaak werden toegevoegd en verwijderd, en een gekoppelde lijst presteerde beter dan een array.
3) Kun je het verschil uitleggen tussen enkelvoudig gekoppelde lijsten en dubbelvoudig gekoppelde lijsten?
Verwacht van kandidaat: De interviewer wil uw conceptuele helderheid en uw vermogen om technische verschillen duidelijk uit te leggen toetsen.
Voorbeeld antwoord: Een enkelvoudig gekoppelde lijst heeft knooppunten die alleen naar het volgende knooppunt wijzen, terwijl een dubbel gekoppelde lijst knooppunten heeft die naar zowel het volgende als het vorige knooppunt wijzen. Dubbel gekoppelde lijsten maken achterwaartse traversering eenvoudiger, maar vereisen meer geheugen vanwege de extra pointer.
4) Hoe detecteert u een cyclus in een gekoppelde lijst?
Verwacht van kandidaat: Dit test je probleemoplossende vaardigheden en je bekendheid met veelvoorkomende algoritme-patronen.
Voorbeeld antwoord: Een veelgebruikte methode is het gebruik van twee pointers die met verschillende snelheden bewegen, vaak de 'langzame en snelle pointer'-techniek genoemd. Als er een cyclus ontstaat, zullen de twee pointers elkaar uiteindelijk ontmoeten. In een eerder artikel heb ik deze methode gebruikt om oneindige lussen in een dataverwerkingspipeline te voorkomen.
5) Wat zijn enkele veelvoorkomende bewerkingen die op gekoppelde lijsten worden uitgevoerd?
Verwacht van kandidaat: De interviewer wil weten of u de standaardprocedures en hun implicaties begrijpt.
Voorbeeld antwoord: Veelvoorkomende bewerkingen zijn invoegen, verwijderen, doorlopen, zoeken en omkeren van de lijst. Elke bewerking heeft een andere tijdscomplexiteit, afhankelijk van waar deze wordt uitgevoerd. Dit is belangrijk bij het ontwerpen van efficiënte systemen.
6) Hoe ga je te werk bij het invoegen van een knooppunt midden in een gekoppelde lijst?
Verwacht van kandidaat: Ze testen je begrip van het manipuleren van muisaanwijzers en je oog voor detail.
Voorbeeld antwoord: Om een knooppunt in het midden in te voegen, doorloop ik eerst de lijst om de gewenste positie te vinden. Vervolgens pas ik de pointers aan, zodat het nieuwe knooppunt naar het volgende knooppunt wijst en het vorige knooppunt naar het nieuwe knooppunt. Zorgvuldige aanpassingen van de pointers zijn cruciaal om te voorkomen dat de lijst beschadigd raakt.
7) Beschrijf een situatie waarin een gekoppelde lijst prestatieproblemen veroorzaakte en hoe u dit hebt opgelost.
Verwacht van kandidaat: Deze gedragsvraag evalueert uw vermogen om te reflecteren en te optimaliseren.
Voorbeeld antwoord: Bij mijn vorige baan werd een gekoppelde lijst gebruikt voor veelvoorkomende zoekopdrachten, wat leidde tot trage prestaties. Ik heb het probleem vastgesteld en aanbevolen over te stappen op een hash-gebaseerde structuur, waardoor de zoektijden aanzienlijk verbeterden.
8) Hoe zou je een gekoppelde lijst omkeren?
Verwacht van kandidaat: De interviewer test uw logisch denkvermogen en uw begrip van iteratieve of recursieve benaderingen.
Voorbeeld antwoord: Ik zou een gekoppelde lijst omkeren door er doorheen te itereren en de 'next'-pointer van elk knooppunt te wijzigen zodat deze naar het vorige knooppunt wijst. Dit proces wordt herhaald totdat alle pointers zijn omgekeerd en de kop is bijgewerkt.
9) Wat zijn de voor- en nadelen van het gebruik van gekoppelde lijsten?
Verwacht van kandidaat: Ze willen een evenwichtig perspectief en inzicht in de afwegingen die gemaakt moeten worden.
Voorbeeld antwoord: De voordelen zijn onder andere dynamische grootte en efficiënte invoegingen en verwijderingen. De nadelen zijn een hoger geheugenverbruik en tragere toegangstijden in vergelijking met arrays. In mijn vorige functie hielp het begrijpen van deze afwegingen me bij het kiezen van de juiste structuur voor verschillende componenten.
10) Hoe bepaal je welk type gekoppelde lijst je in een systeemontwerp moet gebruiken?
Verwacht van kandidaat: Deze situationele vraag beoordeelt de besluitvorming in architectonische contexten.
Voorbeeld antwoord: Ik houd rekening met factoren zoals de benodigde doorlooptijden, geheugenbeperkingen en de frequentie van bewerkingen. Als bijvoorbeeld achterwaartse doorloop vereist is, is een dubbelgelinkte lijst geschikter, terwijl een enkelgelinkte lijst volstaat voor eenvoudigere, geheugenefficiënte implementaties.
