В этой серии «Структуры данных в 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.

  1. Перейти по связанному списку
  2. Удалить дубликаты из связанного списка
  3. Получить k-й элемент до последнего из связанного списка
  4. Удалить узел из связанного списка
  5. Добавьте два связанных списка слева направо
    например 1- ›2-› 3 + 8- ›7 =› 321 + 78 = 399
  6. Добавьте два связанных списка справа налево
    например 1- ›2-› 3 + 8- ›7 =› 123 + 87 = 210

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

В следующем посте я расскажу о стопках и очередях.