在 python 中显示双向循环链表时遇到问题

Question

我目前正在 python 中学习数据结构，但在 display() 中遇到问题 CircularDoublyLinkedList class

中的方法

while循环运行通过重复CircularDoublyLinkedListclass

的元素无限循环

#my code:
class Node:
    def __init__(self,value):
        self.value=value
        self.next=None
        self.prev=None

class CircularDoublyLinkedList:
    def __init__(self):
        self.head=None
        self.tail=None

    def display(self):
        if self.head is None:
            return 'Circular doubly Linked list doesn\'t exists'
        else:
            node=self.head
            elements=[]
            while node:
                if node==self.tail:
                    break
                elements.append(node.value)
                print(node.value)
                node=node.next
        return elements

    def insertnode(self,value,position):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.tail=node
            self.prev=node
            self.next=node
        else:
            if position==0:
                node.prev=self.tail
                node.next=self.head
                self.head=node
                self.head.prev=node
                self.tail.next=node
            elif position==-1:
                node.next=self.head
                node.prev=self.tail
                self.tail=node
                self.tail.next=node
                self.head.prev=node
            else:
                index=0
                tempnode=self.head
                while index<position-1:
                    tempnode=tempnode.next
                    index+=1
                node.next=tempnode.next
                node.prev=tempnode
                node.next.prev=node
                tempnode.next=node

#creating objects

cdll=CircularDoublyLinkedList()
cdll.insertnode(5,0)
cdll.insertnode(0,0)
cdll.insertnode(1,-1)
cdll.insertnode(2,2)

print(cdll.display())

我尝试将 display() 方法中的 if 条件从 node==self.tail 更改为 node==self.tail.next 但没有任何改变

那么如何解决 class CircularDoublyLinkedList 的 display() 方法中的这个错误？

任何帮助将不胜感激...谢谢

Answer 1

当下一个节点是列表的 head 时，display() 内的循环必须停止：

    def display(self):
        if self.head is None:
            return 'Circular doubly Linked list doesn\'t exists'
        else:
            node=self.head
            elements=[]
            while node:
                elements.append(node.value)
                print(node.value)
                node=node.next
                if node==self.head: break
        return elements

检查方法insertnode()以确保它是正确的！我认为它不能正常工作。

Answer 2

有几个问题：

在 display 中，break 应该在之后出现 你打印了 tail 值。所以这个循环应该是这样的：

while node: elements.append(node.value) print(node.value) if node==self.tail: break node=node.next

在 insertnode 中，对于第一种情况，您分配给 self.prev 和 self.next，但这些不属于 [=21= 的属性] （这是一个链表实例，而不是节点实例）。相反，你想要：

node.prev=node node.next=node

在insertnode中，对于第二种情况，你不应该在赋值给self.head.prev之前改变self.head。所以交换这些语句，得到这个顺序：

self.head.prev=node self.head=node

在insertnode中，对于剩余的情况，您遇到与上一点类似的问题：首先分配给self.tail.next，然后才移动self.tail参考，所以你得到这个执行顺序：

self.tail.next=node self.tail=node

通过这些修复，您的代码将按预期工作。

其他备注和备选方案

在循环双向链表中不需要尾部引用，因为在非空列表中 self.tail 总是将等于self.head.prev。所以真的没有充分的理由将它维护在一个单独的属性中。省略它可以使代码更短而不会降低效率。

由于循环双向链表中没有节点具有 prev 或 next 的 None 值，因此使用自引用初始化这些属性更为自然Node 构造函数。

在方法内部打印并不是很好：它将链表逻辑与 I/O 问题混合在一起。相反，通过实现 __iter__ 方法使链表可迭代，并在主程序代码中保留打印。

insertnode 的代码可以减少，只需确定 node.next 必须是什么，然后所有其余的“接线”就可以在所有情况下通用。唯一的例外是将节点添加到空列表时。

应用这些点我们得到：

class Node: def __init__(self, value): self.value = value self.next = self.prev = self # No None in a doubly linked list class CircularDoublyLinkedList: def __init__(self): self.head = None # No tail needed def __iter__(self): # iterator is useful for many scenarios node = self.head if node: yield node.value while node.next != self.head: node = node.next yield node.value def insertnode(self, value, position): node = Node(value) if not self.head: self.head = node # node is already correctly wired return node.next = self.head if position == 0: self.head = node while position > 0: # No need for an index variable node.next = node.next.next position -= 1 # Common code: node.prev = node.next.prev node.prev.next = node.next.prev = node cdll = CircularDoublyLinkedList() cdll.insertnode(5, 0) cdll.insertnode(0, 0) cdll.insertnode(1, -1) cdll.insertnode(2, 2) print(*cdll) # Use iterator for displaying

在 python 中显示双向循环链表时遇到问题

having problem in displaying doubly circular linked list in python

python

linked-list

data-structures

其他备注和备选方案