Vejledning til Python-interviewspørgsmål: hvordan man koder en linket liste

Jeg har altid forstået kernekonceptet med sammenkædede lister, men jeg har aldrig omsat 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 oversatte til kode.

Og det er derfor, jeg skriver denne guide!

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

Jeg ønsker at dække en række spørgsmål om sammenkædede lister, og denne artikel er det første skridt i denne proces. Så lad os dykke ind.

Hvad er en sammenkædet liste?

En sammenkædet liste er en datastruktur, der består af mange mini-datastrukturer kaldet 'Noder'. Knudepunkterne knytter sig sammen for at danne en liste.

Hver node indeholder 2 attributter

  1. Dens værdi. Dette kan være hvad som helst: heltal, tegn, strenge, objekter osv.
  2. En markør til den næste node i sekvensen.

Nogle definitioner

'Hovedknude': Hovedknuden er simpelthen den første knude på den sammenkædede liste. Som vi kan se fra eksemplet ovenfor, er noden, der indeholder '5', den første node og derfor hovedet.

'Tail Node': Halenoden er den sidste node i sekvensen. Da det er den sidste node, peger den på null, fordi der ikke er nogen næste node i sekvensen. I eksemplet ovenfor ville noden indeholdende '3' være hale node.

Enkeltkoblet vs Dobbeltkoblet

Når det kommer til sammenkædede lister, er der to hovedtyper.

Dem, der er 'enkeltvis' forbundet, og dem, der er 'dobbelt' forbundet.

Enkelt forbundet betyder, at hver node kun peger på højst 1 anden node, noden foran den. Dette er vist i eksemplet ovenfor.

Dobbelt forbundet betyder, at hver node kan pege på 2 andre noder, noden foran den og noden bag den. Som vi kan se fra eksemplet nedenfor, da der ikke er nogen knudepunkt forud for hovedknudepunktet (som er 5), peger en af ​​dens markører på null.

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

Kodning af sammenkædede lister kan være et problem med 4 linjer eller et problem med 400 linjer. Det afhænger af, hvordan du vil nærme dig det.

På det enkleste niveau, som vi diskuterede, er en sammenkædet liste bare en masse forbundne noder.

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

class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNode

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

For at oprette en knude overfører vi simpelthen 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 angiver node1 til node2:

“3” → “7”

Den anden linje ovenfor gør node2 til node3:

“7” → ”10”

Alt i alt har vi en sammenkædet liste, der ser sådan ud:

“3” → ”7” → ”10” → Null

Bemærk: “10” peger på null, fordi der ikke var tildelt nogen nextNode til node3, og standard nextNode er Null.

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.

Gennemgang af en sammenkædet liste

Hvis du laver et programmeringsinterview, og du bliver bedt om et Linked List-spørgsmål, får du ikke alle noderne.

Alt hvad du får er hovednoden.

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

First let’s understand how to get the value and nextNode from a node in Python.

Let’s say we have a node simply named ‘node’.

Getting the value of the node:

node.value

Getting the nextNode of the node:

node.nextNode

Traversal

This first thing we want to do is create a variable called “currentNode” that keeps track of the node we’re at. We want to assign this to our head node at first.

currentNode = head

Now all we have to do is simply check whether or not our current node is Null. If it’s not, we make our ‘currentNode’ equal to the ‘nextNode’ of the ‘currentNode’.

currentNode = node1while currentNode is not None: currentNode = currentNode.nextNode

Let’s say we have the following Linked List: “3”→”7"→”10".

Our head and first ‘currentNode’ is “3”.

When we do

currentNode = currentNode.nextNode

We are reassigning ‘currentNode’ to our current node’s neighbor, which in this case is “7”.

This continues until the currentNode is pointed to None, in which case the loop stops.

And that is the basic way to traverse through a Linked List in Python.

Link to the code on Github.

Inserting elements

When you insert an element into a linked list, you insert it into the back unless specified otherwise.

Let’s use the following example:

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

Let’s say we want to insert a “4”.

We would simply find the tail node, in this case “10”, and set its nextNode to our “4” node.

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

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

Now let’s say we were in an interview, and all we had was the head node.

We simply traverse through the LinkedList to find the tail. Once we have the tail, we simply set its nextNode to our new node that we create.

def insertNode(head, valuetoInsert): currentNode = head while currentNode is not None: if currentNode.nextNode is None: currentNode.nextNode = linkedListNode(valuetoInsert) return head currentNode = currentNode.nextNode

Deleting elements

Deleting can get a bit tricky.

Let’s take the same example.

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

If we wanted to delete the “7”, all we need to do is point the “3” to the “10” so that the “7” is never referenced.

“3”→”10"→Null

To do this, we would have to traverse the list while not only keeping track of the currentNode, but also keeping track of the previousNode.

We would also have to account for the head node being the node we want to delete.

In the code below, we simply delete the first instance of the value we want to delete.

Note that there are many ways to accomplish this, and the solution below might not be the cleanest code you’ll see in your life. However, in the heat of an interview, the interviewer probably won’t expect textbook perfect code.

def deleteNode(head, valueToDelete): currentNode = head previousNode = None while currentNode is not None: if currentNode.value == valueToDelete: if previousNode is None: newHead = currentNode.nextNode currentNode.nextNode = None return newHead # Deleted the head previousNode.nextNode = currentNode.nextNode return head previousNode = currentNode currentNode = currentNode.nextNode return head # Value to delete was not found.

In the code above, once we find the node we want to delete, we set the previous node’s “nextNode” to the deleted node’s “nextNode” to completely cut it out of the list.

Big O Time Complexity Analysis

**NOTE** These are the time complexities for the node structure above, which is most likely to appear on an interview. In practical cases, you can store attributes in a LinkedList class to lower these complexities.

‘n’ = the amount of elements inside the Linked List.

Inserting to the back of the Linked List— We go through all n elements to find the tail and insert our new node. O(n)

Inserting to the front of the Linked List — We simply create the new node and set its nextNode to the head. No need to traverse the list. O(1)

Traversing — We go through all n elements once. O(n)

Deleting — Worst case scenario, the node we’re deleting is the last node, causing us to traverse through the entire list. O(n)

Du kan nu tackle spørgsmål om linkede interviewinterviews!

Du har nu den grundlæggende viden, du har brug for for at begynde at tackle Linked List-interviewspørgsmål!

De kan starte let og blive meget hurtige.

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

Hvis du er studerende, der ønsker at lande din drømme praktik 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 sig frem til deres drømmejob.

Tak for læsningen, og held og lykke!