🧊 Фундаментальные структуры данных: массивы и связанные списки с реализацией на Python

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

Массивы

Массивы – одна из самых фундаментальных структур данных в информатике. Они встроены во все языки программирования, даже такие низкоуровневые, как C или Assembler. Массивы представляют собой группу элементов одного типа, которые расположены на непрерывном участке памяти компьютера. Например, [5, 8, -1] или ['a', 'b', 'c'].

Поскольку элементы массива стоят рядом друг с другом, мы можем получить доступ к любому их индексу. Например, к первому, третьему или последнему элементу за время O(1).

В таких языках, как C и Java, требуется заранее указывать размер массива и тип данных. Структура списка в Python позволяет обойти эти требования, сохраняя данные в виде указателей на местоположение элементов в памяти, автоматически изменяя размер массива, когда место заканчивается. Элементам памяти не обязательно находиться рядом друг с другом.

Реализация

Основные ограничения, с которыми мы сталкиваемся при создании массивов на языке Python:

1. После выделения места для массива мы не можем получить больше, не создав новый массив.
2. Все значения в массиве должны быть одного типа.

Мы можем реализовать в Python очень простой класс Array, который имитирует основную функциональность массивов в языках более низкого уровня.

from typing import Any

class Array:
    def __init__(self, n: int, dtype: Any):
        self.vals = [None] * n
        self.dtype = dtype

    def get(self, i: int) -> Any:
        """
        Возвращает значение как индекс i
        """
        return self.vals[i]

    def put(self, i: int, val: Any) -> None:
        """
        Обновляем массив как индекс i с val. Val должно быть одного типа с self.dtype
        """
        if not isinstance(val, self.dtype):
            raise ValueError(f"val явл {type(val)}; должно быть {self.dtype}")

        self.vals[i] = val

Давайте рассмотрим, какие способы реализации класса Array мы можем использовать. Создадим экземпляр. Подтвердим, что первый индекс пустой. Заполним слот символом char, а затем вернем его. Наши предыдущие действия подтвердили, что массив отвергает non-char (несимвольные) значения. Код не самый лучший, но рабочий:

arr = Array(10, str)

arr.get(0)       # None
arr.put(0, 'a')  # None
arr.get(0)       # 'a'

arr.put(1, 5)    
# ValueError: val is <class 'int'>; must be <class 'str'>

Пример

В процессе работы с массивами вы, скорее всего, захотите использовать встроенный список Python, или массив NumPy, а не созданный нами класс Array. Однако, в целях использования массива, который не меняет размер, необходимо разобраться с Leetcode LC 1089: Duplicate Zeros (Дублирование нулей). Цель данных действий – продублировать все нули в массиве, изменяя его на месте таким образом, чтобы элементы двигались вниз и исчезали, а не увеличивали размер массива или создавали новый.

def duplicate_zeros(arr: list) -> None:
    """
    Дублируем все нули в массиве, оставляя его первоначальную     длину. Например, [1, 0, 2, 3] -> [1, 0, 0, 2]
    """
    i = 0

    while i < len(arr):
        if arr[i] == 0:
            arr.insert(i, 0)   # Вставляем 0 как индекс i
            arr.pop()          # Убираем последний элемент
            i += 1
        i += 1

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

Обратите внимание: в данном случае важно использовать цикла while, а не for, так как мы изменяем массив по мере его прохождения. Тщательный контроль над индексом i позволяет нам пропустить вставленный ноль, чтобы избежать двойного счета.

Связанные списки

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

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

Ниже представлен связанный список со значениями [1, 'a', 0.3]. Обратите внимание на различие размеров элементов. Мы видим четыре байта для целых и плавающих чисел, один байт для символов. Каждый узел имеет четырехбайтовый указатель, расстояние между узлами различно, последний из них содержит нулевой указатель, который указывает в пространство.

Отсутствие ограничений на типы данных и длину делает связанные списки привлекательными. Однако эта гибкость создает некоторые проблемы. Программе доступен только верх списка, а это значит, что для поиска любого другого узла нам придется пройти весь список. Другими словами, мы лишаемся O(1) поиска для любого элемента, кроме первого узла. Если вы запрашиваете 100-й элемент, то для его получения потребуется 100 шагов: схема O(n).

Можно сделать связанные списки более универсальными. Для этого необходимо добавить указатели на предыдущие узлы и раскрыть конец списка, или сделать его кольцевым. В целом, выбор связанных списков вместо массивов является платой за удобство.

Реализация

Чтобы создать связанный список в Python, начнем с определения узла. Необходимы только две части: данные, которые хранит узел и указатель на следующий узел в списке. Добавим метод __repr__ для того, чтобы было легче увидеть содержание узла.

class ListNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"ListNode со значением {self.val}"

Далее попробуем использовать класс ListNode. Важно отметить, что вершина списка – это наша переменная head. Необходимо итеративно добавлять .next для доступа к более глубоким узлам, поскольку мы не можем ввести индекс типа [1] или [2], чтобы добраться до них.

head = ListNode(5)
head.next = ListNode('abc')
head.next.next = ListNode(4.815162342)

print(head)            # ListNode со значением 5
print(head.next)       # ListNode со значением abc
print(head.next.next)  # ListNode со значением 4.815162342

Для того чтобы было легче добавить узел как в конец, так и в начало списка, напишем функции:

def add_to_end(head: ListNode, val: Any) -> None:
    ptr = head
    while ptr.next:
        ptr = ptr.next
    ptr.next = ListNode(val)

def add_to_front(head: ListNode, val: Any) -> ListNode:
    node = ListNode(val)
    node.next = head
    return node

В add_to_end создаем переменную ptr (указатель). Она начинается с head и обходит список, пока не достигнет последнего узла, атрибутом .next которого является нулевой указатель. Далее, устанавливаем значение .next этого узла в новый ListNode. Внутри функции не нужно ничего возвращать, чтобы изменение вступило в силу.

В add_to_front мы создаем новый head, устанавливаем указатель .next в вершину существующего связанного списка. Вручную обновляем head вне данной функции с помощью нового узла. В противном случае, head по-прежнему будет указывать на старый head.

# Создает и расширяет список
head = ListNode(5)
add_to_end(head, 'abc')
add_to_end(head, 4.815162342)

# Вывод
print(head)            # ListNode со значением 5
print(head.next)       # ListNode со значением abc
print(head.next.next)  # ListNode со значением 4.815162342

# Пытаемся обновить head
add_to_front(head, 0)  
print(head)            # ListNode со значением 5

# Корректное обновление head
head = add_to_front(head, 0)
print(head)            # ListNode со значением 0

Пример

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

Ранее мы использовали указатель, чтобы обойти список по одному узлу за раз, пока не дойдем конца.

На самом деле существует способ найти середину списка за один проход.

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

Исходя из написанного выше, мы ответим на LC 876: Середина связанного списка (Middle of the Linked List) следующим образом:

def find_middle(head: ListNode) -> ListNode:
    """
    Return middle node of linked list. If even number of nodes,
    returns the second middle node.
    """
    # Смотрим на медленную и быструю точки
    slow = head
    fast = head.next

    # Прогоняем список через цикл
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow 

В данном случае при работе с Leetcode, мы убеждаемся, что head.next – правильный вариант.

# Список: A -> B -> C -> D -> E
# Середина: C

# Начало с head: неправильно
# Slow: A -> B -> C -> D  ==> Середина: D
# Fast: A -> C -> E -> null

# Начало с head.next: правильно
# Slow: A -> B -> C       ==> Середина: C
# Fast: B -> D -> null

LC 141. Linked List Cycle: Цикл связанного списка – пример использования медленных и быстрых указателей. Наша цель определить, есть ли в списке цикл, который возникает, когда следующий указатель узла показывает на более ранний узел в списке.

Проблема в том, что проход списка через цикл будет бесконечным.

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

Более простой подход заключается в использовании двух указателей.

В данном случае невозможно использование while fast и fast.next, так как эти методы имеют значение False только при достижении конца списка. Вместо этого, подставим slow и fast на первый и второй узлы. Будем перемещать их по списку с разной скоростью, пока они не совпадут. В конце списка вернем False. Если два указателя будут показывать на один и тот же узел, вернем True.

def has_cycle(head: ListNode) -> bool:
    """
    Определяем где связанный список имеет цикл
    """
    slow = head
    fast = head.next

    while slow != fast:

        # Находим конец списка
        if not (fast or fast.next):
            return False

        slow = slow.next
        fast = fast.next.next

    return True

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

В следующей части материала приступим к изучению деревьев и графов.

Материалы по теме

• 📈 Big O нотация: что это такое и почему ее обязательно нужно знать каждому программисту
  
• Какие алгоритмы нужно знать, чтобы стать хорошим программистом?
• Изучаем алгоритмы: полезные книги, веб-сайты, онлайн-курсы и видеоматериалы

Источники

• https://towardsdatascience.com/intro-to-data-structures-2615eadc343d