Python链表实现和对象建模

Question

我正在尝试在Python上实现单链表，下面的代码可以正常工作，但我不明白它是如何工作的：

class Node(object):
    def __init__(self, data=None, ):
        self.value = data
        self.next = None

class LinkedList1(object):
    def __init__(self, data=None):
        self.head = Node(data)
        self.tail = self.head
        self.length = 1

    def append(self, data):
        self.tail.next = Node(data)
        self.tail = self.tail.next
        self.length += 1
        return self

    def show_list(self):
        head_copy = self.head
        while head_copy is not None:
            print(head_copy.value)
            head_copy = head_copy.next

当我们测试它时：

linkin = LinkedList1(10)
linkin.append(20)
linkin.append(30)
linkin.append(40)
linkin.show_list()

输出：

10
20
30
40

我不理解的是append函数。我知道self.tail引用了self.head，但是为什么self.tail.next会在最后一个next处添加新的Node(data)，按照我的逻辑，没有循环的情况下应该添加到第一个next。

另外，如果我们这样编写函数：

def append(self, data):
        self.head.next = Node(data)
        self.tail = self.head.next
        self.length += 1
        return self

即使self.tail引用self.head，这也不起作用。

我知道我在这里缺少了什么。你能帮我理解吗？

谢谢。

- MertTheGreat

Answer 1

self.tail只在存在单个节点时设置为self.head。tail总是被更改以指向最后一个节点，这与头结点相同，仅在添加第二个节点之前才会发生。

每次调用append时，tail都会更改以指向刚添加的节点。

把元素附加到第一个节点似乎没有太多意义，对吧？那样会摆脱列表的其余部分。

让我们逐行看一下：

def append(self, data):
        self.tail.next = Node(data)

在执行此操作之前，self.tail.next 的值为 None，表示列表到此结束。现在，我们已将其设置为一个新的节点，该新节点具有一个值为 None 的 "next" 值。

         self.tail = self.tail.next

由于self.tail需要指向列表中的最后一项，因此我们需要对其进行更改。因此，上述行将其更改为指向新的最后一项。

         self.length += 1
         return self

这些仅仅是用来追踪长度并返回的。只要做得正确，你就不需要遍历列表来知道其中有多少个节点。

- Garr Godfrey

---

好的解释，你的意思是尾引用保存所有的下一个节点吗？ - MertTheGreat

它不包含所有的下一个节点。列表中的每个节点只包含一个“next”，指向列表中的下一个项目。尾部始终没有下一个节点，因为它是最后一个节点，后面没有任何内容。 - Garr Godfrey

Answer 2

如果您提到类Node，它有两个对象：value和next Node。

在链表实现中，它是这样实现的，尾节点信息也被存储。在附加函数中，self.tail.next = Node(data)基本上在尾节点之后添加了一个新节点，并且self.tail = self.tail.next将链表的尾节点重新分配给新创建的节点（现在是列表的最后一个节点）。

例如，让我们看一下以下代码：

linkin = LinkedList1(10)
linkin.append(20)
linkin.append(30)
linkin.append(40)
linkin.show_list()

1. 使用self.head -> Node(10)和self.tail -> Node(10)创建了一个链表。
2. 添加20会改变链表：self.head -> Node(10)，self.tail.next -> Node(20) [等同于self.head.next]，10 -> 20，其中10是头部，20是尾部。
3. 添加30会改变链表：self.tail.next -> Node(30) [这里的self.tail是Node(20)]，并将Node(30)设置为尾部，10 -> 20 -> 30，其中10是头部，30是尾部。

希望这有所帮助。

- Gowtham Venkat