Guida alle domande dell'intervista Python: come codificare un elenco collegato

Ho sempre compreso il concetto centrale delle liste collegate, ma non l'ho mai messo in pratica.

Non è stato fino alla mia prima intervista su Amazon, anni fa, quando ho capito che non avevo idea di come il concetto di liste collegate si traducesse in codice.

Ed è per questo che sto scrivendo questa guida!

Il mio obiettivo è aiutarti a trovare un lavoro come ingegnere del software.

Vorrei trattare molte domande dell'intervista di elenchi collegati e questo articolo è il primo passo in questo processo. Quindi tuffiamoci.

Cos'è un elenco collegato?

Un elenco collegato è una struttura di dati costituita da molte strutture di mini-dati denominate "nodi". I nodi si collegano insieme per formare un elenco.

Ogni nodo contiene 2 attributi

  1. Il suo valore. Può essere qualsiasi cosa: numeri interi, caratteri, stringhe, oggetti e così via.
  2. Un puntatore al nodo successivo nella sequenza.

Alcune definizioni

Il "nodo principale": il nodo principale è semplicemente il primo nodo nell'elenco collegato. Come possiamo vedere dall'esempio sopra, il nodo contenente "5" è il primo nodo, e quindi la testa.

Il "nodo di coda": il nodo di coda è l'ultimo nodo della sequenza. Poiché è l'ultimo nodo, punta a null, perché non esiste un nodo successivo nella sequenza. Nell'esempio sopra, il nodo contenente "3" sarebbe il nodo di coda.

Collegato singolarmente vs Collegato doppiamente

Quando si tratta di elenchi collegati, ci sono due tipi principali.

Quelli che sono collegati "singolarmente" e quelli che sono collegati "doppiamente".

Collegato singolarmente significa che ogni nodo punta al massimo a un altro nodo, il nodo davanti ad esso. Questo è mostrato nell'esempio sopra.

Doppio link significa che ogni nodo può puntare ad altri 2 nodi, il nodo davanti e il nodo dietro di esso. Come possiamo vedere dall'esempio seguente, poiché non vi è alcun nodo che precede il nodo head (che è 5), uno dei suoi puntatori punta a null.

Ok, capisco tutto questo. Ma come funziona il codice?

Coding Linked List può essere un problema di 4 righe o un problema di 400 righe. Dipende da come ti vuoi avvicinare.

Al livello più semplice, come abbiamo discusso, un elenco collegato è solo un gruppo di nodi collegati.

Quindi, tutto ciò di cui abbiamo veramente bisogno per creare questa struttura è un oggetto nodo.

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

Qui possiamo vedere che abbiamo semplicemente creato una classe che ha un valore e un attributo nextNode.

Per creare un nodo, passiamo semplicemente un valore.

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

Qui, abbiamo creato 3 singoli nodi.

Il passo successivo è semplicemente collegarli insieme.

node1.nextNode = node2 node2.nextNode = node3 

La prima riga sopra fa sì che node1 punti a node2:

"3" → "7"

La seconda riga in alto fa in modo che node2 punti a node3:

"7" → "10"

Tutti insieme, ci rimane un elenco collegato simile a questo:

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

Nota: "10" punta a null, perché non è stato assegnato alcun nextNode a node3 e il nextNode predefinito è Null.

Come ho detto prima, ci sono molti modi diversi per farlo. Questo è solo il più semplice.

Se stai cercando di creare un'intera classe LinkedList, questo video spiega in dettaglio come farlo.

Attraversare un elenco collegato

Se stai facendo un colloquio di programmazione e ti viene posta una domanda su un elenco collegato, non ti verranno dati tutti i nodi.

Tutto ciò che otterrai è il nodo principale.

Da quel nodo principale, devi ottenere il resto della lista.

Per prima cosa capiamo come ottenere il valore e nextNode da un nodo in Python.

Supponiamo di avere un nodo chiamato semplicemente "nodo".

Ottenere il valore del nodo:

node.value

Ottenere il nextNode del nodo:

node.nextNode

Traversal

La prima cosa che vogliamo fare è creare una variabile chiamata "currentNode" che tenga traccia del nodo in cui ci troviamo. Inizialmente vogliamo assegnarlo al nostro nodo principale.

currentNode = head

Ora tutto ciò che dobbiamo fare è semplicemente controllare se il nostro nodo corrente è o meno Null. Se non lo è, rendiamo il nostro "currentNode" uguale al "nextNode" di "currentNode".

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

Supponiamo di avere il seguente elenco collegato: "3" → "7" → "10".

La nostra testa e il primo "currentNode" è "3".

Quando lo facciamo

currentNode = currentNode.nextNode

Stiamo riassegnando "currentNode" al prossimo del nostro nodo corrente, che in questo caso è "7".

Questo continua finché il currentNode non punta a None, nel qual caso il ciclo si ferma.

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!