tail 如何在链接结构中工作？

Question

我是编程新手，我正在使用 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

我希望我的问题足够清楚。我非常感谢你的时间。谢谢！

Answer 1

After this line of code, the self._tail becomes the second element and this seems pretty logical as I have to keep tracking the tail as I keep on adding elements and self._head now have two elements but in code there is no line of code where to self._head is added a new element.

我认为您可能在这里遗漏的是 self._head 本身不是 Bag，而是指向 _BagListNode object.

的指针

当新物品被添加到包中时，它们作为下一个节点附加在前一个尾巴上，成为新的尾巴。这根本不会影响您的实施中的头部。另一种可能更清晰的实现可以简单地使一个项目成为列表的新头部，如图所示：

我的数据结构教授给我的一个技巧是画出正在发生的事情的图片，以提高您的直觉理解。你可以考虑画一幅图，画出当第三件物品被放入包中时会发生什么。

tail 如何在链接结构中工作？

How tail works within a linked structures?

python

list

data-structures

tail

head