как закодировать связанный список

1656634452 kak zakodirovat svyazannyj spisok

Энтони Систилли

AaEcjameCBwOPORpaQgAighYgKoz5jTn6PxZ
Фото Майка Алонзо на Unsplash

Я всегда понимал основную концепцию связанных списков, но никогда не применял ее на практике.

Лишь в моем первом интервью на Amazon несколько лет назад я понял, что понятия не имею, как концепция связанных списков переводится на код.

hTliWmiFIsrEJqgzgpkHffXflO3tkNIUa5-E
*Мое лицо во время моего первого интервью в Amazon*

И потому я пишу это руководство!

Моя цель – помочь ты получить работу инженера-программиста.

Я хочу рассмотреть многие вопросы, касающиеся интервью со связанными списками, и эта статья является первым шагом в этом процессе. Давайте погрузимся.

Что такое связанный список?

Связанный список – это структура данных, состоящая из многих мини-структур данных, называемых «узлами». Узлы соединяются для создания списка.

QUIARoltvUdLReB8VIoNcGFPkaAvGwDWOl8d
Полный связанный список, состоящий из 3 узлов, связанных вместе.

Каждый узел содержит 2 атрибута.

  1. Его ценность. Это может быть что угодно: целые числа, знаки, строчки, объекты и т.П.
  2. Указатель на следующий узел в последовательности.

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

«Главный узел»: Главный узел – это просто первый узел в связанном списке. Как мы можем видеть на примере выше, узел, содержащий «5», является первым узлом, а следовательно, головой.

«Хвостовой узел»: Хвостовой узел является последним узлом в последовательности. Поскольку это последний узел, он указывает на null, потому что следующего узла в последовательности нет. В приведенном выше примере узел, содержащий «3», будет являться хвостовым узлом.

Односвязанный против двойной связи

Что касается связанных списков, то существует два основных типа.

Те, которые связаны «одно» и связаны «двойно».

Одиночно связаны означает, что каждый узел указывает только один узел, узел перед ним. Это показано в примере выше.

Yii0EYpRWc8SQO4mOq0Lejev6T8uTe4unJfv
Пример односвязанного списка.

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

ucPAE2WqQmZiN1dIkbtr4LpONEZW-UPPnPyI
Пример двухсвязного списка.

Ладно, я все понимаю. Но как работает код?

Кодирование связанных списков может быть a Задание на 4 строчки или задание на 400 строк. Это зависит от того, как вы хотите подойти к этому.

На самом простом уровне, как мы обсуждали, связанный список – это просто a куча соединенных узлов.

Таким образом, все, что нам действительно нужно для создания этой структуры, – это узловой объект.

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

Здесь мы видим, что мы просто создали класс, имеющий значение и атрибут nextNode.

Чтобы создать узел, мы просто передаем значение.

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

Здесь мы создали 3 отдельных узла.

Следующим шагом будет просто соединить их вместе.

node1.nextNode = node2 node2.nextNode = node3 

В первой строке выше узел1 указывает на узел2:

«3» → «7»

Во второй строке выше node2 указывает на node3:

“7”→”10”

В общем, у нас остался связанный список, который выглядит так:

“3”→”7”→”10”→Ноль

Примечание: «10» указывает на нуль, поскольку узлу 3 не был назначен nextNode, а по умолчанию nextNode имеет значение Null.

Как я уже упоминал ранее, есть много разных способов сделать это. Это как раз самое простое.

Если вы пытаетесь создать целый класс LinkedList, это видео подробно рассказывает, как это сделать.

Обход связанного списка

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

Все, что вы получите – это главный узел.

05jgbOs3qG84t7qmpEd-Ubhl9QyQgYWUiiV-
Все, что здесь передается, это главный узел.

С этого главного узла вы должны получить оставшийся список.

Сначала давайте разберемся, как получить значение и 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».

Это продолжается, пока текущий узел не будет указан на None, в этом случае цикл останавливается.

Это основной способ перехода через связанный список в Python.

Ссылка на код Github.

Вставка элементов

Когда вы вставляете элемент в связанный список, вы вставляете его сзади, если не указано иное.

Воспользуемся следующим примером:

“3”→”7”→”10”→Ноль

Скажем, мы хотим вставить «4».

Мы бы просто обнаружили хвост узла, в данном случае «10», и установили его nextNode на наш узел «4».

“3”→”7”→”10”→“4”→Ноль

node4 = linkedListNode("4")node3.nextNode = node4

Теперь, скажем, мы были на собеседовании и все, что у нас было, это главный узел.

Мы просто проходим список LinkedList, чтобы найти хвост. Когда у нас есть хвост, мы просто устанавливаем его nextNode на наш новый узел, который мы создаем.

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

Удаление элементов

Удаление может быть несколько сложным.

Возьмем тот же пример.

“3”→”7”→”10”→Ноль

Если мы хотим удалить «7», все, что нам нужно сделать, это указать «3» на «10», чтобы «7» никогда не упоминался.

“3”→”10”→Ноль

Чтобы сделать это, мы должны пройти список, не только отслеживая текущий узел, но и отслеживая предварительный узел.

Нам также придется учитывать главный узел, который мы хотим удалить.

В коде ниже мы просто удаляем первый экземпляр значения, которые мы хотим удалить.

Обратите внимание, что есть много способов достичь этого, и следующее решение может быть не самым чистым кодом, который вы увидите в своей жизни. Однако в разгар собеседования интервьюер, вероятно, не ожидает, что идеальный код учебника.

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.

В коде выше, когда мы находим узел, который хотим удалить, мы устанавливаем nextNode предыдущего узла на nextNode удаленного узла, чтобы полностью вырезать его из списка.

Big O Time Complexity Analysis

**ПРИМЕЧАНИЕ** Это временные сложности для вышеуказанной структуры узла, которая, скорее всего, появится на собеседовании. На практике можно сохранять атрибуты в классе LinkedList, чтобы уменьшить эти сложности.

‘n’ = количество элементов в соответствующем списке.

Вставка в конце связанного списка Мы проходим через все n элементы, чтобы найти хвост и вставить наш новый узел. O(n)

Вставка в начало связанного списка — Мы просто создаем новый узел и устанавливаем его nextNode в голову. Не нужно просматривать список. О(1)

Траверс Перебираем все n элементы один раз. O(n)

Удаление В худшем случае, узел, который мы удаляем, является последним узлом, заставляющим нас пройти весь список. O(n)

Теперь вы можете отвечать на вопросы для собеседования по связанному списку!

Теперь у вас есть фундаментальные знания, необходимые для того, чтобы начать отвечать на вопросы собеседования по связанному списку!

Они могут начать легко и очень быстро стать жесткими.

В следующей статье я собираюсь рассмотреть несколько часто задаваемых вопросов и методы, которыми можно воспользоваться для их решения.

Если вы студент и хотите получить стажировку своей мечты или полный рабочий день в течение следующих 2 лет, начните практиковать сейчас!

Я основал сообщество (www.theforge.ca), где мы объединяем студентов с наставниками и экспертами отрасли, которые помогают им сориентироваться на пути к работе мечты.

Спасибо за чтение и желаю удачи!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *