Блог

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

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

 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()
 

Когда вы повторно добавляете существующий узел в список, вы ничего не делаете с существующими узлами, которые уже ссылались на повторно добавленный узел. В вашем случае теперь у вас есть узел в конце списка, который next указывает обратно на узел, который только что стал head , и поэтому теперь ваш список является циклическим, что приведет к тому, что любая функция, которая пытается обойти список, будет infaloop.

Я могу придумать три способа решить эту проблему, и я оставлю лучшее напоследок:

1. Добавьте логику обнаружения цикла, чтобы защитить вас от повторения цикла, когда ваш список становится циклическим (т. Е. Разорвать циклы или просто прекратить обход, как только вы вернетесь туда, где вы уже были). Это нетривиально, и IMO не является отличным решением; лучше, чтобы список не был поврежден в первую очередь, чем постоянно проверять, нуждается ли он в исправлении.
2. Добавьте removeNode функцию, чтобы убедиться, что данный узел был полностью удален из списка (т. Е. Путем сканирования всего списка, чтобы увидеть, какие другие узлы, если таковые имеются, ссылаются на данный узел, и настраивают указатели, чтобы пропустить его). Затем вы можете безопасно повторно вставить узел, предварительно удалив его. Примечание: если вызывающий абонент передает вам узел, который принадлежит ДРУГОМУ списку, у вас все равно могут возникнуть проблемы, потому что у вас не будет возможности найти этот другой список! Циклические структуры по-прежнему будут возможны путем создания списков, а затем вставки узлов каждого в другой.
3. Не разрешайте вызывающим ваш класс list вообще получать доступ к фактическим узлам; попросите их вставлять значения (а не узлы), чтобы вы могли убедиться, что они никогда не дают вам узел со странными значениями указателя (узел, который принадлежит другому списку, узел, который указывает на себя, И т. Д.). Указатели должны быть полностью внутренними для вашего класса связанного списка, а не чем-то, что вызывающий может испортить.

Вкратце, согласно вашему коду, бесконечный цикл, с которым вы сталкиваетесь, возникает из-за того, что 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 значение упоминания узла 1, и фигура отверстия становится:

 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.
 

Это объяснение бесконечного цикла, с которым вы сталкиваетесь.

Удачи