在 LinkedList 中两次插入相同的节点会触发无限循环

Question

我想了解为什么在单向链表中两次插入同一个节点会导致无限循环。

我尝试插入最后一个节点作为新的头节点。但是当我运行代码时，它开始了一个我可以看到的无限循环，因为我调用了一个方法来在最后打印节点。这是我的代码。

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


class LinkedList:
    def __init__(self):
        self.head = None

    def insertLast(self, newNode):
        if self.head is None:
            self.head = newNode
        else:
            lastNode = self.head
            while True:
                if lastNode.next is None:
                    break
                lastNode = lastNode.next
            lastNode.next = newNode

    def insertHead(self, newNode):
        # x, y ,z. => new head, x,y,z
        if self.head is None:
            print("List is empy please call inserlast()")
        else:

            currentHead = self.head
            self.head = newNode
            self.head.next = currentHead

    def printList(self):
        if self.head is None:
            print("EMPTY List. No Data found!")
            return
        else:
            currentNode = self.head
            while True:
                print(currentNode.data)
                currentNode = currentNode.next
                if currentNode is None:
                    break


node1 = Node("Head")
node2 = Node("Some Data")
node3 = Node("Some More Data")

# I am adding this node at the end of the list
newnode1 = Node("New Head")

linkedList = LinkedList()

# create a new linked list by inserting at end
linkedList.insertLast(node1)
linkedList.insertLast(node2)
linkedList.insertLast(newnode1)

# using a node i have already added in the list as New head of the list
linkedList.insertHead(newnode1)
linkedList.printList()

Answer 1

当您将现有节点重新添加到列表时，您不会对已经引用重新添加的节点的现有节点执行任何操作。在你的例子中，你现在在列表的末尾有一个节点，它的 next 指向刚刚变成 head 的节点，所以现在你的列表是循环的，这将导致任何试图遍历列表到 infaloop 的函数。

我可以想到三种方法来解决这个问题，我会把最好的留到最后：

添加循环检测逻辑，以保护您在列表变为循环时不会陷入循环（即打破循环或在您回到已经去过的地方后停止遍历）。这很重要，IMO 不是一个很好的解决方案；最好从一开始就防止列表被破坏，而不是不断检查它是否需要修复。
添加一个removeNode函数以确保给定节点已从列表中完全删除（即通过扫描整个列表以查看其他节点（如果有的话）引用给定节点，并调整指针以跳过它）。然后您可以通过先移除节点来安全地重新插入节点。注意：如果调用者传递给你一个属于不同列表的节点，你仍然会遇到麻烦，因为你无法找到另一个列表！通过构建列表然后将每个节点插入另一个，循环结构仍然是可能的。
根本不允许列表 class 的调用者访问实际节点；让他们插入值（而不是节点），这样您就可以确保他们永远不会为您提供具有奇怪指针值的节点（属于另一个列表的节点，指向自身的节点等）。指针应该完全在您的链表内部 class 而不是调用者可能搞砸的东西。

Answer 2

简单地说，根据您的代码，您面临的无限循环是由于 The linked list does not arrange the nodes physically, it just tells each node which node is next.

下面详细解释一下：

如图所示，每个节点都有一个 next 属性，由 LinkedList 设置到下一个节点。

启动节点后

node1.next mentions to None
node2.next mentions to None
newnode1.next mentions to None

创建链表后

node1.next mention to Node2
node2.next mention to Newnode1
newnode1.next mention to None

再次插入Newnode1作为头后，链表集合Nownode1.next提及到Node1，孔图变为：

node1.next mention to Node2
node2.next mention to Newnode1
newnode1.next mention to Node1

因此，它成为一个闭环

The linked list does not arrange the nodes physically, it just tells each node which node is next.

这就是你面临的无限循环的解释。

祝你好运

在 LinkedList 中两次插入相同的节点会触发无限循环

Inserting same node twice in LinkedList triggers infinite loop

python

linked-list

singly-linked-list