Vraaggids voor Python-interviews: hoe een gekoppelde lijst te coderen

Ik heb het kernconcept van Linked Lists altijd begrepen, maar ik heb het nooit in de praktijk gebracht.

Pas bij mijn allereerste Amazon-interview, jaren geleden, besefte ik dat ik geen idee had hoe het concept van Linked Lists in code werd vertaald.

En daarom schrijf ik deze gids!

Mijn doel is om jou te helpen aan een baan als Software Engineer.

Ik wil veel interviewvragen van Linked Lists behandelen, en dit artikel is de eerste stap in dat proces. Dus laten we erin duiken.

Wat is een gekoppelde lijst?

Een gekoppelde lijst is een datastructuur die bestaat uit vele mini-datastructuren die 'Nodes' worden genoemd. De knooppunten zijn aan elkaar gekoppeld om een ​​lijst te vormen.

Elk knooppunt bevat 2 attributen

  1. Zijn waarde. Dit kan van alles zijn: gehele getallen, tekens, tekenreeksen, objecten, enzovoort.
  2. Een aanwijzer naar het volgende knooppunt in de reeks.

Enkele definities

Het ' hoofdknooppunt ': het hoofdknooppunt is gewoon het eerste knooppunt in de gekoppelde lijst. Zoals we in het bovenstaande voorbeeld kunnen zien, is het knooppunt met '5' het eerste knooppunt en daarom het hoofd.

Het ' staartknooppunt ': het staartknooppunt is het laatste knooppunt in de reeks. Omdat het het laatste knooppunt is, wijst het naar nul, omdat er geen volgend knooppunt in de reeks is. In het bovenstaande voorbeeld zou het knooppunt met '3' het staartknooppunt zijn.

Singly Linked vs Dubbel Linked

Als het gaat om gekoppelde lijsten, zijn er twee hoofdtypen.

Degenen die 'afzonderlijk' met elkaar verbonden zijn, en degenen die 'dubbel' verbonden zijn.

Enkelvoudig gekoppeld betekent dat elk knooppunt slechts naar maximaal 1 ander knooppunt wijst, het knooppunt ervoor. Dit wordt getoond in het bovenstaande voorbeeld.

Dubbel gekoppeld betekent dat elk knooppunt naar 2 andere knooppunten kan wijzen, het knooppunt ervoor en het knooppunt erachter. Zoals we in het onderstaande voorbeeld kunnen zien, wijst een van de verwijzingen naar nul, aangezien er geen knooppunt vóór het hoofdknooppunt is (dat is 5).

Oké, dat begrijp ik allemaal. Maar hoe werkt de code?

Het coderen van gekoppelde lijsten kan een probleem met 4 lijnen of een probleem met 400 lijnen zijn. Het hangt ervan af hoe u het wilt benaderen.

Op het eenvoudigste niveau, zoals we hebben besproken, is een gekoppelde lijst slechts een aantal verbonden knooppunten.

Het enige dat we dus echt nodig hebben om deze structuur te maken, is een knooppuntobject.

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

Hier kunnen we zien dat we zojuist een klasse hebben gemaakt met een waarde en een nextNode-attribuut.

Om een ​​knooppunt te maken, geven we eenvoudig een waarde door.

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

Hier hebben we 3 individuele knooppunten gemaakt.

De volgende stap is om ze eenvoudig met elkaar te verbinden.

node1.nextNode = node2 node2.nextNode = node3 

De eerste regel hierboven laat knooppunt1 naar knooppunt2 wijzen:

"3" → "7"

De tweede regel hierboven laat knooppunt2 naar knooppunt3 wijzen:

"7" → "10"

Alles bij elkaar hebben we een gekoppelde lijst die er als volgt uitziet:

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

Opmerking: "10" verwijst naar null, omdat er geen nextNode is toegewezen aan node3 en de standaard nextNode is Null.

Zoals ik al eerder zei, zijn er veel verschillende manieren om dit te doen. Dit is gewoon de eenvoudigste.

Als je een hele LinkedList-klas probeert te maken, gaat deze video dieper in op hoe je dat moet doen.

Een gekoppelde lijst doorkruisen

Als je een programmeerinterview doet en je een Linked List-vraag krijgt, krijg je niet alle knooppunten.

Het enige dat u krijgt, is het hoofdknooppunt.

Van dat hoofdknooppunt moet je de rest van de lijst ophalen.

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)

You can now tackle Linked List interview questions!

You now have the fundamental knowledge you need to start tackling Linked List interview questions!

They can start off easy, and get tough really quick.

In the next article, I’m going to go over a couple of common questions and techniques you can use to solve them.

If you’re a student looking to land your dream internship or full-time job within the next 2 years, start practicing now!

I’ve started a community (www.theforge.ca) where we connect students with mentors and industry experts that help them navigate their way to their dream job.

Thanks for reading, and good luck!