Spørgsvejledning til Python-interview: hvordan man kode en linket liste

Foto af Mike Alonzo på Unsplash

Jeg har altid forstået kernekonceptet med Linked Lists, men jeg har aldrig brugt det i praksis.

Det var først i mit allerførste Amazon-interview for mange år siden, da jeg indså, at jeg ikke havde nogen idé om, hvordan begrebet Linked Lists blev oversat til kode.

* Mit ansigt under mit første Amazon-interview nogensinde *

Og det er derfor, jeg skriver denne vejledning!

Mit mål er at hjælpe dig med at få et job som softwareingeniør.

Jeg vil dække en masse spørgsmål om sammenhængende lister, og denne artikel er det første trin i denne proces. Så lad os dykke ind.

Hvad er en linket liste?

En tilknyttet liste er en datastruktur, der består af mange mini-datastrukturer kaldet ‘Noder.’ Knudepunkterne kobles sammen for at danne en liste.

En hel tilknyttet liste, der består af 3 noder, der er knyttet sammen.

Hver knude indeholder 2 attributter

  1. Dets værdi. Dette kan være alt: heltal, karakterer, strenge, objekter og så videre.
  2. En markør til den næste knude i sekvensen.

Nogle definitioner

'Head Node': Hovednoden er simpelthen den første knude på den linkede liste. Som vi kan se af eksemplet ovenfor, er den node, der indeholder '5' den første knude, og derfor hovedet.

'Tail Node': Hale-noden er den sidste knude i sekvensen. Da det er den sidste knude, peger det på null, fordi der ikke er nogen næste knude i sekvensen. I eksemplet ovenfor ville noden, der indeholder '3' være haleknudepunktet.

Enkelt forbundet vs dobbelt forbundet

Når det kommer til lænkede lister, er der to hovedtyper.

De, der er "enkeltvis" knyttet, og dem, der er "dobbelt" forbundet.

Enkelt koblet betyder, at hver knude kun peger på højst 1 anden knude, knuden foran den. Dette er vist i eksemplet ovenfor.

Et eksempel på en enkelt linket liste.

Dobbeltkoblet betyder, at hver knude kan pege på 2 andre knudepunkter, noden foran den og knuden bag den. Som vi kan se af eksemplet nedenfor, da der ikke er nogen knude, der går foran hovedknuden (som er 5), peger et af dets pointer til null.

Et eksempel på en dobbeltkædet liste.

Okay, jeg forstår alt det her. Men hvordan fungerer koden?

Kodning af linkede lister kan være et 4-linjeproblem eller et 400 linjeproblem. Det afhænger af, hvordan du vil henvende dig til det.

På det enkleste niveau, som vi diskuterede, er en sammenkoblet liste bare en masse tilsluttede noder.

Således er alt, hvad vi virkelig har brug for for at oprette denne struktur, et nodeobjekt.

klasse linkedListNode:
    def __init __ (self, value, nextNode = None):
        self.value = værdi
        self.nextNode = nextNode

Her kan vi se, at vi blot har oprettet en klasse, der har en værdi og nextNode-attribut.

For at oprette en node, indtaster vi blot en værdi.

node1 = linkedListNode ("3") # "3"
node2 = linkedListNode ("7") # "7"
node3 = linkedListNode ("10") # "10"

Her har vi oprettet 3 individuelle noder.

Det næste trin er simpelthen at forbinde dem sammen.

node1.nextNode = node2
node2.nextNode = node3

Den første linje ovenfor får node1 til punkt 2:

“3” → “7”

Den anden linje ovenfor gør node2 til node3:

”7” →”10"

Vi har alle sammen en linket liste, der ser sådan ud:

”3” →”7" →” 10" → Null

Bemærk: “10” peger på null, fordi der ikke blev tildelt nogen næste knude til node3, og standard næste knap er Nul.

Som jeg nævnte tidligere, er der mange forskellige måder at gøre dette på. Dette er bare det enkleste.

Hvis du prøver at lave en hel LinkedList-klasse, går denne video i dybden om, hvordan du gør det.

Gennemse en linket liste

Hvis du laver en programmeringssamtale, og du bliver stillet et spørgsmål om en tilknyttet liste, får du ikke alle noder.

Det eneste, du får, er hovednoden.

Alt der bliver sendt her er hovednoden.

Fra denne hovedknude skal du hente resten af ​​listen.

Lad os først forstå, hvordan du får værdien og næste knap fra en knude i Python.

Lad os sige, at vi har en knude, der blot hedder 'node'.

Henter noden værdi:

node.value

Henter næste knudepunkt for noden:

node.nextNode

Traversal

Denne første ting, vi gerne vil gøre, er at oprette en variabel kaldet “nuværende knudepunkt”, der holder styr på den node, vi er på. Vi vil først tildele dette til vores hovedknude.

strømnode = hoved

Nu skal vi blot kontrollere, om vores nuværende knudepunkt er Nul eller ikke. Hvis det ikke er tilfældet, gør vi vores 'nuværende knudepunkt' lig med 'næste knudepunkt' for 'nuværende knudepunkt'.

currentNode = node1
mens nuværende kode ikke er Ingen:
    currentNode = currentNode.nextNode

Lad os sige, at vi har følgende linkede liste: “3” → ”7” → ”10”.

Vores hoved og første 'nuværende kode' er '3'.

Når vi gør det

currentNode = currentNode.nextNode

Vi tildeler 'nuværende knudepunkt' til vores nuværende knudepunktsnabo, som i dette tilfælde er '7'.

Dette fortsætter, indtil den nuværende knap er peget på Ingen, i hvilket tilfælde løkken stopper.

Og det er den grundlæggende måde at krydse gennem en linket liste i Python.

Link til koden på Github.

Indsættelse af elementer

Når du indsætter et element i en linket liste, indsætter du det på bagsiden, medmindre andet er angivet.

Lad os bruge følgende eksempel:

”3” →”7" →” 10" → Null

Lad os sige, at vi ønsker at indsætte en "4".

Vi ville simpelthen finde halenoden, i dette tilfælde “10”, og indstille dens næste knude til vores “4” knude.

”3” →”7" →” 10" → ’4’ → Null

node4 = linkedListNode ("4")
node3.nextNode = node4

Lad os nu sige, at vi var i et interview, og alt hvad vi havde var hovednoden.

Vi kører ganske enkelt gennem LinkedList for at finde halen. Når vi først har halen, indstiller vi simpelthen dens næste knudepunkt til vores nye knude, som vi opretter.

def insertNode (head, valuetoInsert):
    strømnode = hoved
    mens nuværende kode ikke er Ingen:
        hvis currentNode.nextNode er Ingen:
            currentNode.nextNode = linkedListNode (valuetoInsert)
            vend hovedet tilbage
        currentNode = currentNode.nextNode

Sletning af elementer

Sletning kan blive lidt vanskelig.

Lad os tage det samme eksempel.

”3” →”7" →” 10" → Null

Hvis vi ønskede at slette “7”, er alt, hvad vi skal gøre, at pege “3” til “10”, så der ikke henvises til “7”.

”3” →”10" → Null

For at gøre dette, er vi nødt til at krydse listen, mens vi ikke kun holder styr på den aktuelle kode, men også holder styr på den forrige knude.

Vi bliver også nødt til at redegøre for, at hovednoden er den knude, vi vil slette.

I koden herunder sletter vi simpelthen den første forekomst af den værdi, vi vil slette.

Bemærk, at der er mange måder at gøre dette på, og løsningen nedenfor muligvis ikke er den reneste kode, du ser i dit liv. Imidlertid i interviewets hede forventer intervieweren sandsynligvis ikke den perfekte kode i lærebogen.

def deleteNode (head, valueToDelete):
    strømnode = hoved
    previousNode = Ingen
    mens nuværende kode ikke er Ingen:
        hvis currentNode.value == valueToDelete:
            hvis previousNode er Ingen:
                newHead = currentNode.nextNode
                currentNode.nextNode = Ingen
                return newHead # Slettet hovedet
            previousNode.nextNode = currentNode.nextNode
            vend hovedet tilbage
        previousNode = currentNode
        currentNode = currentNode.nextNode
    returhoved # Værdi til sletning blev ikke fundet.

Når koden ovenfor er fundet, når vi finder den node, vi vil slette, indstiller vi den forrige nodes “næste knudepunkt” til den slettede knudepunkt “næste knude” for at skære den helt ud af listen.

Big O Time Complexity Analyse

** BEMÆRK ** Dette er tidskompleksiteterne for nodestrukturen ovenfor, som sandsynligvis vises på et interview. I praktiske tilfælde kan du gemme attributter i en LinkedList-klasse for at sænke disse kompleksiteter.

‘N’ = mængden af ​​elementer på den linkede liste.

Indsættelse bag på den linkede liste - Vi går gennem alle n-elementer for at finde halen og indsætte vores nye knude. På)

Indsætning foran på den linkede liste - Vi opretter blot den nye knude og sætter dens næste knude til hovedet. Ingen grund til at krydse listen. O (1)

Traversing - Vi gennemgår alle n elementer én gang. På)

Sletning - I værste tilfælde er den node, vi sletter, den sidste node, der får os til at gå gennem hele listen. På)

Du kan nu tackle spørgsmål om sammenhængende liste!

Du har nu den grundlæggende viden, du har brug for, for at begynde at tackle problemstillinger med Linked List interview!

De kan starte let og blive hårde virkelig hurtige.

I den næste artikel vil jeg gå over et par almindelige spørgsmål og teknikker, du kan bruge til at løse dem.

Hvis du er en studerende, der ønsker at lande dit drømmepraktik eller fuldtidsjob inden for de næste 2 år, skal du begynde at øve nu!

Jeg har startet et samfund (www.theforge.ca), hvor vi forbinder studerende med mentorer og brancheeksperter, der hjælper dem med at navigere deres vej til deres drømmejob.

Tak for læsningen og held og lykke!