В этой серии «Структуры данных в Python» я расскажу о 6 основных структурах данных, которые могут возникнуть в любом виде собеседований при приеме на работу / стажировке инженера-программиста. Это связанные списки, стеки / очереди, хэши, кучи и деревья.
Я выбрал Python в качестве основного языка для этой серии из-за его удобочитаемости и простоты реализации структур данных. Фактически, и Гарвард, и Массачусетский технологический институт предлагают свои вводные курсы CS на Python.
Сегодня я расскажу о связанных списках. Вы можете найти исходный код для задач кодирования ниже здесь. Давайте начнем.
Что такое связанный список?
Вот изображение связанного списка. Следует отметить два важных момента:
1: связанный список состоит из узлов.
2: каждый узел состоит из значения и указателя на другой узел.
Начальный узел связанного списка называется заголовком.
По сути, связанный список - это цепочка значений, связанных с указателями.
Зачем использовать связанные списки?
Связанный список часто сравнивают с массивами. В то время как массив представляет собой последовательность фиксированного размера, в связанном списке могут быть элементы для динамического распределения. Каковы плюсы и минусы этих характеристик? Вот несколько основных:
Преимущества
Связанный список экономит память. Он выделяет только память, необходимую для сохранения значений. В массивах вы должны установить размер массива, прежде чем заполнять его значениями, что потенциально может привести к потере памяти.
Узлы связанного списка могут находиться где угодно в памяти. В то время как массив требует инициирования последовательности памяти, пока ссылки обновляются, каждый узел связанного списка можно гибко перемещать на другой адрес.
Недостатки
Время линейного поиска. При поиске значения в связанном списке вы должны начинать с начала цепочки и проверять один элемент за раз на предмет значения, которое вы ищете. Если связанный список состоит из n элементов, это может занять до n времени. Напротив, многие языки допускают постоянный поиск в массивах.
Связанные списки в Python
Вот как реализовать связанный список в Python:
Это класс узла.
class Node: def __init__(self,val): self.val = val self.next = None # the pointer initially points to nothing
Когда у вас есть класс Node, вы можете реализовать любой связанный список следующим образом:
node1 = Node(12) node2 = Node(99) node3 = Node(37) node1.next = node2 # 12->99 node2.next = node3 # 99->37 # the entire linked list now looks like: 12->99->37
Вы могли спросить, почему я не реализовал класс LinkedList. В конце концов, связанный список - это просто набор узлов, соединенных вместе. Мы можем ссылаться на узел заголовка как на связанный список, который начинается оттуда. В приведенном выше примере node1 является узлом заголовка, и он также может представлять связанный список, который начинается с него. Если вам интересна реализация с использованием класса LinkedList, загляните сюда.
Перемещение значений
class Node: ... def traverse(self): node = self # start from the head node while node != None: print node.val # access the node value node = node.next # move on to the next node
Ценности можно перемещать так. Вы начинаете с головного узла, проверяете его значение и переходите к следующему узлу. Как только вы дойдете до конца связанного списка, узел не должен иметь никакого значения (None).
Боковое примечание: странно говорить о связанных списках в Python, потому что эта структура данных слишком низкого уровня, чтобы быть полезной в программах на Python. Так что не вините меня, если вы не видите смысла кодировать все это на Python. В конце концов, нет особого смысла в использовании связанного списка в Python, кроме его образовательной ценности и полезности при программировании собеседований. На других языках, таких как C и C ++, где связанные списки действительно важны для любых программ, которые вы реализуете.
[Дополнительно] Двусвязные списки
Как следует из названия, каждый узел в двусвязном списке имеет два узла: один указывает на следующий узел, а другой указывает на предыдущий узел. Вот реализация Python:
class
DoublyNode: def
__init__(self, val): self.val =
data self.next
=
None self.prev =
None
Преимущества перед односвязным списком
1) Можно перемещать как в прямом, так и в обратном направлении.
2) Удаление операция более эффективна (взгляните на p4 ниже и сравните его с операцией удаления для двусвязного списка).
Недостатки перед односвязным списком
1) Каждый узел требует дополнительного места для предыдущего указателя.
2) Все операции требуется поддерживать дополнительный указатель.
Некоторые проблемы с кодированием связанных списков
Вот задачи, которые помогут вам лучше познакомиться со связанными списками. Большинство задач взяты из книги Cracking the Coding Interview.
- Перейти по связанному списку
- Удалить дубликаты из связанного списка
- Получить k-й элемент до последнего из связанного списка
- Удалить узел из связанного списка
- Добавьте два связанных списка слева направо
например 1- ›2-› 3 + 8- ›7 =› 321 + 78 = 399 - Добавьте два связанных списка справа налево
например 1- ›2-› 3 + 8- ›7 =› 123 + 87 = 210
Мои решения можно найти здесь. Не стесняйтесь присылать мне пул-реквест или оставлять здесь комментарии, если у вас есть какие-либо вопросы или вы обнаружили ошибки в моих решениях.
В следующем посте я расскажу о стопках и очередях.