Python循环双向链表CircularDoublyLinkedList的display()方法死循环如何解决

问题原因分析 #

你的代码存在两处核心问题：

1. insertnode方法存在逻辑错误 #

• 空链表插入第一个节点时，错误地给链表实例本身新增了prev/next属性，没有给新节点设置自引用的前后指针，导致链表结构从初始化就出错
• 头部、尾部插入节点时，修改self.head/self.tail指向的顺序错误，先修改了实例的头尾指针再调整旧节点的引用，导致旧节点的指针没有被正确更新，进一步打乱了循环链表的结构

2. display方法遍历逻辑不完整 #

现有逻辑遇到尾节点就直接跳出循环，没有把尾节点的值加入结果集，而且如果链表结构异常的情况下很容易出现死循环。

修复后的完整代码 #

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'
        node=self.head
        elements=[]
        # 循环遍历直到回到头节点，说明已经走完全部节点
        while True:
            elements.append(node.value)
            print(node.value)
            node=node.next
            if node == self.head:
                break
        return elements

    def insertnode(self,value,position):
        node=Node(value)
        if self.head is None:
            self.head=node
            self.tail=node
            # 给节点自身设置循环引用，不是给链表实例加属性
            node.prev=node
            node.next=node
        else:
            if position==0:
                node.prev=self.tail
                node.next=self.head
                # 先调整旧头节点和尾节点的指针，再修改头节点指向
                self.head.prev=node
                self.tail.next=node
                self.head=node
            elif position==-1:
                node.next=self.head
                node.prev=self.tail
                # 先调整旧尾节点和头节点的指针，再修改尾节点指向
                self.tail.next=node
                self.head.prev=node
                self.tail=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

# 创建对象测试
cdll=CircularDoublyLinkedList()
cdll.insertnode(5,0)
cdll.insertnode(0,0)
cdll.insertnode(1,-1)
cdll.insertnode(2,2)

print(cdll.display())

输出结果 #

0
5
2
1
[0, 5, 2, 1]

内容的提问来源于stack exchange，提问作者Super Ultra Noob