Ръководство за въпроси за интервю за Python: как да кодирате свързан списък

Винаги съм разбирал основната концепция на свързаните списъци, но никога не съм я прилагал на практика.

Едва при първото ми интервю с Amazon преди години разбрах, че нямам представа как концепцията за свързаните списъци се превежда в код.

И затова пиша това ръководство!

Целта ми е да ви помогна да си намерите работа като софтуерен инженер.

Искам да разгледам много въпроси за интервюта за свързани списъци и тази статия е първата стъпка в този процес. Така че нека се потопим.

Какво е свързан списък?

Свързаният списък е структура от данни, която се състои от много структури с мини данни, наречени „Възли“. Възлите се свързват заедно, за да образуват списък.

Всеки възел съдържа 2 атрибута

  1. Стойността му. Това може да бъде всичко: цели числа, символи, низове, обекти и т.н.
  2. Указател към следващия възел в последователността.

Някои определения

„Главният възел“: Главният възел е просто първият възел в свързания списък. Както виждаме от примера по-горе, възелът, съдържащ „5“, е първият възел и следователно главата.

'Опашният възел': Опашният възел е последният възел в последователността. Тъй като това е последният възел, той сочи към нула, тъй като в поредицата няма следващ възел. В горния пример възелът, съдържащ „3“, ще бъде възелът на опашката.

Единично свързани срещу двойно свързани

Що се отнася до свързаните списъци, има два основни вида.

Тези, които са „единично“ свързани, и тези, които са „двойно“ свързани.

Единично свързан означава, че всеки възел сочи само към най-много 1 друг възел, възела пред него. Това е показано в горния пример.

Двойно свързано означава, че всеки възел може да сочи към 2 други възела, възела пред него и възела зад него. Както можем да видим от примера по-долу, тъй като няма възел, предхождащ главния възел (който е 5), един от неговите указатели сочи към null.

Добре, разбирам всичко това. Но как работи кодът?

Кодирането на свързани списъци може да бъде проблем с 4 реда или проблем с 400 реда. Зависи от това как искате да подходите.

На най-простото ниво, както обсъждахме, свързаният списък е просто куп свързани възли.

По този начин всичко, от което наистина се нуждаем, за да създадем тази структура, е обект на възел.

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

Тук можем да видим, че просто сме създали клас, който има атрибут value и nextNode.

За да създадем възел, ние просто предаваме стойност.

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

Тук създадохме 3 отделни възли.

Следващата стъпка е просто да ги свържете заедно.

node1.nextNode = node2 node2.nextNode = node3 

Първият ред по-горе прави node1 точка към node2:

“3” → “7”

Вторият ред по-горе прави node2 точка към node3:

“7” → ”10"

Всички заедно ни остава свързан списък, който изглежда така:

“3” → ”7” → ”10” → Нула

Забележка: “10” сочи към null, тъй като към node3 не е присвоен nextNode, а по подразбиране nextNode е Null.

Както споменах по-рано, има много различни начини да направите това. Това е просто най-простото.

Ако се опитвате да направите цял клас LinkedList, това видео се задълбочава как да го направите.

Преминаване през свързан списък

Ако правите интервю за програмиране и ви бъде зададен въпрос за свързан списък, няма да получите всички възли.

Всичко, което ще получите, е главният възел.

От този главен възел трябва да вземете останалата част от списъка.

Първо нека разберем как да получим стойността и nextNode от възел в Python.

Да предположим, че имаме възел, наречен просто „възел“.

Получаване на стойността на възела:

node.value

Получаване на nextNode на възела:

node.nextNode

Обхождане

Първото нещо, което искаме да направим, е да създадем променлива, наречена „currentNode“, която проследява възела, в който се намираме. Първо искаме да присвоим това на нашия главен възел.

currentNode = head

Сега всичко, което трябва да направим, е просто да проверим дали текущият ни възел е Null. Ако не е, правим нашия 'currentNode' равен на 'nextNode' на 'currentNode'.

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

Да приемем, че имаме следния свързан списък: “3” → ”7” → ”10”.

Нашата глава и първият „currentNode“ е „3“.

Когато го направим

currentNode = currentNode.nextNode

Преназначаваме 'currentNode' на съседката на текущия ни възел, което в случая е „7“.

Това продължава, докато currentNode не бъде насочен към None, и в този случай цикълът спира.

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!