Связный список на Python: Коты в коробках

    И снова здравствуйте! В преддверии старта курса «Разработчик Python» подготовили для вас небольшой авторский материал о связных списках на Python.



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



    Что такое LinkedList?


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

    Давайте визуализируем сухие определения. Теперь у нас есть коты, которые сидят в коробках. И на каждой коробке написано какая она по порядку и за какой должна стоять.



    Что мы будем делать со связным списком:

    1. Проверять содержится ли в нем тот или иной элемент;
    2. Добавлять узлы в конец;
    3. Получать значение узла по индексу;
    4. Удалять узлы.

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

    Начать придется с создания двух классов:

    class Box:
      def __init__ (self,cat = None):
        self.cat = cat
        self.nextcat = None
    
    class LinkedList:
      def __init__(self):
        self.head = None

    В общем случае, у нас получился узел, у которого есть внутри какое-то значение – кот, и ссылка на следующий узел. То есть в классе Box, соответственно, есть кот и ссылка на следующую коробку. Как и у любого списка, у связного тоже есть начало, а именно head. Поскольку изначально там ничего нет, начальному элементу присваивается значение None.

    Содержится ли элемент в списке




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

    def contains (self, cat):
        lastbox = self.head
        while (lastbox):
          if cat == lastbox.cat:
            return True
          else:
            lastbox = lastbox.nextcat
        return False

    Добавить узел в конец списка




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

     def addToEnd(self, newcat):
        newbox = Box(newcat)
        if self.head is None:
          self.head = newbox
          return
        lastbox = self.head
        while (lastbox.nextcat):
            lastbox = lastbox.nextcat
        lastbox.nextcat = newbox

    Получить узел по индексу




    По индексу catIndex мы хотим получить узел-коробку, но поскольку как такового индекса у узлов не предусмотрено, нужно придумать какую-то замену, а именно переменную, которая будет выполнять роль индекса. Эта переменная – это boxIndex. Мы проходимся по всему списку и сверяем «порядковый номер» узла, и при совпадении его с искомым индексом – выдаем результат.

     def get(self, catIndex):
        lastbox = self.head
        boxIndex = 0
        while boxIndex <= catIndex:
          if boxIndex == catIndex:
              return lastbox.cat
          boxIndex = boxIndex + 1
          lastbox = lastbox.nextcat

    Удалить узел




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

    Поиск начинается с головы списка, то есть с первой по счету коробки, и продолжается, пока коробки не закончатся, то есть пока headcat не станет None. Мы проверяем соответствует ли значение, хранящееся в текущем узле, тому, которое мы хотим удалить. Если нет, то мы просто идем дальше. Однако, если соответствует, то мы удаляем его и «перепривязываем» ссылки, то есть мы удаляем N-ую коробку, при этом коробка N-1 теперь ссылается на коробку N+1.

      def removeBox(self,rmcat):
        headcat = self.head
    
        if headcat is not None:
          if headcat.cat==rmcat:
            self.head = headcat.nextcat
            headcat = None
            return
        while headcat is not None:
          if headcat.cat==rmcat:
            break
          lastcat = headcat
          headcat = headcat.nextcat
        if headcat == None:
          return
        lastcat.nextcat = headcat.nextcat
        headcat = None

    Вот и все, спасибо, что ознакомились с материалом! На самом деле структура LinkedList это не сложно, и важно понимать, как она работает изнутри. Конечно, на Python ее можно было бы реализовать и в lambda-выражениях, это заняло бы гораздо меньше места, однако здесь я преследовала целью объяснить ее строение, и принцип ее работы на Python максимально подробно, а не гнаться за оптимизацией.

    Исходный код можно посмотреть здесь.
    OTUS. Онлайн-образование
    519.12
    Цифровые навыки от ведущих экспертов
    Share post

    Comments 14

      +1
      Тема котов не раскрыта…
        +1
        в первом примере все таки nextbox, а не nextcat. и да, тема котов не раскрыта )
          0
          Простите, а чем Вам collections.deque не угодил?
            0
            А как добавить в середину? (В статье этого использования нет, но в целом это свойство, которое отличает linked list от deque)
              +1
              Например, с помощью deque.insert?
                0
                О как. В 3.5 добавили, не знал, спасибо!
            –2
            А какой великий смысл придумывать свои названия функций вместо стандартных?
            contains вместо __contains__
            get вместо __getitem__
            addToEnd вместо append
            removeBox вместо remove
              0
              Наверно, может быть, в учебных целях?..
              Но тут я с вами согласен. Мне кажется автору стоило сделать еще один шаг и реализовать правильную библиотеку. А в идеале — вообще опубликовать на гитхабе как полностью оформленную библиотеку с тестами. Можно даже как отдельную статью сделать и это новичкам принесёт куда больше практической пользы, чем даже знакомство с этой структурой данных.
              Не помешали бы также тесты производительности по сравнению с штатными списком и деком.
              Ну и пару придирок вдогонку:
              • автору стоило использовать __slots__
              • имеет смысл сделать «ящики» неизменяемыми (immutable), ла еще и на основе typing.NamedTuple. Будет боле по-питоновски.
              • как выше уже намекнули, хорошо бы использовать «магические» методы
              • Не нужно лениться делать нормальные __repr__ и __init__
              • полезно оформить в пакет, прописать зависимости от версии питона,
              • сделать тесты
              • сделать итератор по элементам
              • хранить в контейнере ссылку на последний элемент тоже. Это O(1) по памяти, но делает вставку в конец тоже O(1), а сейчас O(N). Как-то нелогично же.
              • Для собственного развития автора реализовать бы такую же по свойствам структуру на основе словаря, но с бонусом в O(1) для вставки в любое место связного списка. У вас-то сейчас O(N)/
              • Можно сделать ту же структуру на основе бинарного дерева. Посравнивать производительность получившихся структур данных.

              Со всем этим багажом автора с руками оторвёт любая компания, которая набирает джунов.
                0
                На мой взгляд просто назвать методы по-другому потребует минимальных усилий со стороны автора и в то же время сделает использование удобнее, и учебным целям это скорее способствует.
                  0
                  Это безусловно. Я просто попытался понять мотивацию автора в именовании методов. Это не делает идею хорошей.
              +1

              Мне кажется реализация не соответствует изначальному описанию


              По факту в узле есть его значение, а также две ссылки – на предыдущий и на последующий узлы.

              При этом в реализации есть только одна ссылка — на следующий узел.


              class Box:
                def __init__ (self,cat = None):
                  self.cat = cat
                  self.nextcat = None

              И еще неплохо было бы пройтись каким-нибудь валидатором для pep8. Где-то пробел пропущен, где-то отступы отличаются даже в пределах одной функции.

                0
                Ну что вы придираетесь? Автор, наверно, в первый раз что-то на питоне написал и уже хочет нас чему-нибудь полезному научить, а вы просто неблагодарный сноб=). Похвальный альтруизм должен вызывать у вас улыбку. Шутки шутками, а лучше так, чем <что-нибудь плохое> в <неподобающее для этого время и месте> делать.
                  0

                  Это же Хабр, комментарии должны быть полезнее статьи :)
                  Пусть кто-нибудь из новичков прочтет и узнает, что связный список может быть односвязным или двусвязным. А то и кольцевым.

                0
                >Python очень удобный и многогранный язык,
                >но по умолчанию не имеет такой структуры данных как связный список или LinkedList.
                И это ещё один плюс :)

                Only users with full accounts can post comments. Log in, please.