Определение длины связанного списка

Или: важность архитектуры кода в структурах данных

вступление

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

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

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

Конкретная структура данных: связанный список

Как они работают

Для начала давайте взглянем на некоторые технические характеристики связанных списков. Связанный список - это линейная структура данных, информация о которой не хранится вместе в одном блоке в памяти. Вместо этого каждый узел данных в структуре «указывает» на свой последующий узел - процесс, который эффективно «связывает» узлы вместе от начала до конца. Этот процесс придает связанным спискам их характерное свойство «слабосвязанной» и позволяет более эффективно хранить в памяти.

Для каждого связанного списка потребуются объекты узла связанного списка (фактический пакет) и объекты связанного списка (структура, в которой вы храните объекты узла). Единственная информация, которая требуется узлам связанного списка для хранения собственных данных и следующего узла в списке, и единственная информация, которую необходимо сохранить в связанном списке, - это заголовок (первый элемент) структуры и хвост (последний элемент). ) конструкции. Сильфон - самая простая реализация любого класса:

class LinkedListNode(object):
def __init__(self, data):
        """Initialize this binary tree node with the given data."""
        self.data = data
        self.next = None
class LinkedList(object):
def __init__(self, items=None):
        """Initialize this binary search tree."""
        self.head = None
        self.tail = None

Для получения БОЛЬШОЙ дополнительной информации о связанных списках обязательно ознакомьтесь со статьями Вайдехи Джоши часть 1 и часть 2.

Преимущества

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

Кроме того, связанные списки гораздо более эффективно используют память, чем динамические массивы, поскольку для динамических массивов необходимо, чтобы биты были «зарезервированы» при распределении памяти. (Пример: динамическому массиву с 6 элементами может потребоваться зарезервировать 10 бит данных, тогда как для связанного списка в той же ситуации потребуется только 6 бит данных).

Ограничения

Одно из самых больших ограничений связанных списков заключается в том, что, хотя они хранят информацию о голове и хвосте, они не хранят никакой индексируемой информации о каких-либо элементах, содержащихся в структуре. Это может быть чрезвычайно ограничивающим с точки зрения реализации метода linked_list_contains(item), будет иметь временную сложность O (n) в худшем случае (если элемент находится ближе к концу связанного списка), тогда как та же операция в другом виде списка может быть O (1) если индекс известен.

Еще одно интересное ограничение связанных списков состоит в том, что они имеют довольно неэффективные get_length() методы. Опять же, это связано с тем, что сам связанный список может «видеть» только свою голову и хвост, а должен пройти через каждый доступный узел, чтобы получить длину связанного списка.

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

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

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

Хорошая реализация

Вы можете определить в своем классе ванильный get_length() метод, который привязывает свойство размера к вашему экземпляру связанного списка после его вызова. Это все равно будет иметь временную сложность O (n), но вам нужно будет вызвать этот метод только один раз, а затем ваш объект «запомнит» это значение.

Эта реализация все еще имеет некоторые недостатки, так как вам придется повторно вызывать метод get_length() каждый раз, чтобы добавить или удалить узел из вашего связанного списка, что можно рассматривать как O (n) * (количество модификаций).

Лучшая реализация

Большинство классов связанных списков будут иметь методы как для добавления, так и для удаления узлов в цепочку. Поскольку эти методы уже выполняют всю «тяжелую работу» с точки зрения временной сложности (будет O (n), где n - количество узлов, которые нужно добавить / удалить), мы можем хитроумно «совмещать» простую операцию self.size += 1 или self.size -= 1 в эти методы.

Это будет означать, что наше свойство self.size всегда будет актуальным, а доступ к свойству объекта будет иметь временную сложность O (1) - большое улучшение по сравнению с O (n)!

#!python
def append(self, item):
        """Insert the given item at the tail of this linked list."""
        # Create a new node to hold the given item
        new_node = Node(item)
        # Check if this linked list is empty
        if self.is_empty():
            # Assign head to new node
            self.head = new_node
        # Otherwise insert new node after tail
        else:
            self.tail.next = new_node
        # Update tail to new node regardless
        self.tail = new_node
        # Increment self.size
        self.size += 1

Заключение

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

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