Блог

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

 class Bag:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0


 def add(self, item):
        newNode = _BagListNode(item)
        if self._head is None:
            self._head = newNode
        else:
            self._tail.next = newNode
        self._tail = newNode
        self._size  = 1

class _BagListNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None
    def __repr__(self):
        return f"{self.item}"
 

Дело в том, что когда я добавляю первый элемент, все становится понятным. Поскольку сначала head равен None, он добавит newNode как в tail, так и в head . Проблема начинается, когда я добавляю второй элемент: Я не понимаю, почему второй элемент добавляется к элементу, который был добавлен ранее, одновременно с self._tail выполнением этой строки кода self._tail.next = newNode . После этой строки кода self._tail он становится вторым элементом, и это кажется довольно логичным, поскольку я должен продолжать отслеживать хвост, поскольку я продолжаю добавлять элементы, и self._head теперь у меня есть два элемента, но в коде нет строки кода, в которую self._head добавляется новый элемент.

Например:

 bag = Bag()
    bag.add(1)
    bag.add(2)
    bag.add(3)
print(bag._head.item, bag._head.next.item, bag._head.next.next.item)
 

и в результате получается:

 1 2 3
 

Надеюсь, мой вопрос достаточно ясен. Я очень ценю ваше время. Спасибо!

После этой строки кода self._tail становится вторым элементом, и это кажется довольно логичным, поскольку я должен продолжать отслеживать хвост, продолжая добавлять элементы и self.у _head теперь есть два элемента, но в коде нет строки кода, где self ._head добавляется новый элемент.

Я думаю, что вам может не хватать этого self._head — это не пакет сам по себе, а скорее указатель на объект _BagListNode .

Когда новые элементы добавляются в пакет, они прикрепляются как следующий узел к предыдущему хвосту, становясь новым хвостом. Это никак не влияет на head в вашей реализации. Альтернативная, возможно, более понятная реализация может просто сделать элемент новым заголовком списка, как показано здесь:

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