Guide de questions d'entrevue Python: comment coder une liste liée

J'ai toujours compris le concept de base des listes liées, mais je ne l'ai jamais mis en pratique.

Ce n'est qu'à ma toute première interview Amazon il y a des années que j'ai réalisé que je n'avais aucune idée de la façon dont le concept de listes liées se traduisait en code.

Et c'est pourquoi j'écris ce guide!

Mon objectif est de vous aider à trouver un emploi en tant qu'ingénieur logiciel.

Je souhaite couvrir de nombreuses questions d'entrevue liées aux listes liées, et cet article est la première étape de ce processus. Alors plongeons-nous.

Qu'est-ce qu'une liste liée?

Une liste liée est une structure de données constituée de nombreuses mini-structures de données appelées «nœuds». Les nœuds se lient pour former une liste.

Chaque nœud contient 2 attributs

  1. Sa valeur. Cela peut être n'importe quoi: des entiers, des caractères, des chaînes, des objets, etc.
  2. Un pointeur vers le nœud suivant de la séquence.

Quelques définitions

Le «nœud principal»: le nœud principal est simplement le premier nœud de la liste chaînée. Comme nous pouvons le voir dans l'exemple ci-dessus, le nœud contenant '5' est le premier nœud, et donc la tête.

Le «nœud de queue»: le nœud de queue est le dernier nœud de la séquence. Puisqu'il s'agit du dernier nœud, il pointe vers null, car il n'y a pas de nœud suivant dans la séquence. Dans l'exemple ci-dessus, le nœud contenant «3» serait le nœud de queue.

Simple lié vs double lié

En ce qui concerne les listes liées, il existe deux types principaux.

Celles qui sont liées «individuellement» et celles qui sont «doublement» liées.

Simple lié signifie que chaque nœud ne pointe que vers au plus 1 autre nœud, le nœud devant lui. Ceci est illustré dans l'exemple ci-dessus.

Doublement lié signifie que chaque nœud peut pointer vers 2 autres nœuds, le nœud en face et le nœud derrière. Comme nous pouvons le voir dans l'exemple ci-dessous, puisqu'il n'y a pas de nœud précédant le nœud principal (qui vaut 5), l'un de ses pointeurs pointe vers null.

D'accord, je comprends tout cela. Mais comment fonctionne le code?

Le codage des listes liées peut être un problème de 4 lignes ou un problème de 400 lignes. Cela dépend de la façon dont vous voulez l'aborder.

Au niveau le plus simple, comme nous l'avons vu, une liste chaînée n'est qu'un tas de nœuds connectés.

Ainsi, tout ce dont nous avons vraiment besoin pour créer cette structure est un objet nœud.

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

Ici, nous pouvons voir que nous avons simplement créé une classe qui a une valeur et un attribut nextNode.

Pour créer un nœud, nous passons simplement une valeur.

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

Ici, nous avons créé 3 nœuds individuels.

La prochaine étape consiste simplement à les connecter ensemble.

node1.nextNode = node2 node2.nextNode = node3 

La première ligne ci-dessus fait pointer node1 vers node2:

«3» → «7»

La deuxième ligne ci-dessus fait pointer node2 vers node3:

«7» → «10»

Tous ensemble, nous nous retrouvons avec une liste liée qui ressemble à ceci:

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

Remarque: «10» pointe vers null, car aucun nextNode n'a été affecté à node3 et le nextNode par défaut est Null.

Comme je l'ai mentionné plus tôt, il existe de nombreuses façons différentes de procéder. C'est juste le plus simple.

Si vous essayez de créer une classe LinkedList entière, cette vidéo explique en détail comment le faire.

Traverser une liste liée

Si vous faites une entrevue de programmation et qu'une question de liste liée vous est posée, vous n'obtiendrez pas tous les nœuds.

Tout ce que vous obtiendrez est le nœud principal.

À partir de ce nœud principal, vous devez obtenir le reste de la liste.

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!