Python Interview Interview Guide: Wie man eine verknüpfte Liste codiert

Ich habe das Kernkonzept der verknüpften Listen immer verstanden, es aber nie in die Praxis umgesetzt.

Erst bei meinem ersten Amazon-Interview vor Jahren wurde mir klar, dass ich keine Ahnung hatte, wie das Konzept der verknüpften Listen in Code übersetzt wurde.

Und deshalb schreibe ich diesen Leitfaden!

Mein Ziel ist es, Ihnen zu helfen , einen Job als Software Engineer zu bekommen.

Ich möchte viele Interviewfragen zu verknüpften Listen behandeln, und dieser Artikel ist der erste Schritt in diesem Prozess. Also lasst uns eintauchen.

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine Datenstruktur, die aus vielen Minidatenstrukturen besteht, die als "Knoten" bezeichnet werden. Die Knoten werden zu einer Liste verknüpft.

Jeder Knoten enthält 2 Attribute

  1. Dessen Wert. Dies kann alles sein: Ganzzahlen, Zeichen, Zeichenfolgen, Objekte usw.
  2. Ein Zeiger auf den nächsten Knoten in der Sequenz.

Einige Definitionen

Der 'Kopfknoten': Der Kopfknoten ist einfach der erste Knoten in der verknüpften Liste. Wie wir aus dem obigen Beispiel sehen können, ist der Knoten, der '5' enthält, der erste Knoten und daher der Kopf.

Der ' Endknoten ': Der Schwanzknoten ist der letzte Knoten in der Sequenz. Da es der letzte Knoten ist, zeigt er auf null, da es keinen nächsten Knoten in der Sequenz gibt. Im obigen Beispiel wäre der Knoten, der '3' enthält, der Endknoten.

Einfach verbunden vs doppelt verbunden

Wenn es um verknüpfte Listen geht, gibt es zwei Hauptarten.

Diejenigen, die "einzeln" verbunden sind, und diejenigen, die "doppelt" verbunden sind.

Einfach verknüpft bedeutet, dass jeder Knoten nur auf höchstens einen anderen Knoten zeigt, den Knoten davor. Dies ist im obigen Beispiel dargestellt.

Doppelt verknüpft bedeutet, dass jeder Knoten auf zwei andere Knoten zeigen kann, den Knoten davor und den Knoten dahinter. Wie wir aus dem folgenden Beispiel sehen können, zeigt einer seiner Zeiger auf Null, da sich vor dem Kopfknoten (der 5 ist) kein Knoten befindet.

Okay, ich verstehe das alles. Aber wie funktioniert der Code?

Das Codieren verknüpfter Listen kann ein 4-Zeilen-Problem oder ein 400-Zeilen-Problem sein. Es hängt davon ab, wie Sie es angehen möchten.

Auf der einfachsten Ebene besteht eine verknüpfte Liste, wie bereits erwähnt, nur aus einer Reihe verbundener Knoten.

Alles, was wir wirklich brauchen, um diese Struktur zu erstellen, ist ein Knotenobjekt.

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

Hier können wir sehen, dass wir einfach eine Klasse erstellt haben, die einen Wert und ein nextNode-Attribut hat.

Um einen Knoten zu erstellen, übergeben wir einfach einen Wert.

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

Hier haben wir 3 einzelne Knoten erstellt.

Der nächste Schritt besteht einfach darin, sie miteinander zu verbinden.

node1.nextNode = node2 node2.nextNode = node3 

In der ersten Zeile oben zeigt Knoten1 auf Knoten2:

"3" → "7"

In der zweiten Zeile oben zeigt Knoten2 auf Knoten3:

"7" → "10"

Alles in allem bleibt uns eine verknüpfte Liste, die so aussieht:

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

Hinweis: "10" zeigt auf null, da node3 kein nextNode zugewiesen wurde und der standardmäßige nextNode Null ist.

Wie ich bereits erwähnt habe, gibt es viele verschiedene Möglichkeiten, dies zu tun. Dies ist nur das einfachste.

Wenn Sie versuchen, eine gesamte LinkedList-Klasse zu erstellen, wird in diesem Video ausführlich beschrieben, wie das geht.

Durchlaufen einer verknüpften Liste

Wenn Sie ein Programmierinterview durchführen und eine Frage zur verknüpften Liste erhalten, erhalten Sie nicht alle Knoten.

Alles was Sie bekommen ist der Kopfknoten.

Von diesem Kopfknoten müssen Sie den Rest der Liste abrufen.

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!