排序双向链表

Question

我想创建一个 class 带有添加和删除功能的排序，这是我的代码：

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

    def add (self, add_obj):
        newNode=DLLNode(add_obj)
        current=self.head
        if current==None:
            self.head=self.tail=newNode
        else:
            while add_obj>current.data:
                current=current.next_node
            newNode.next_node=current
            newNode.prev_node=current.prev_node
            current.prev_node.next_node=newNode
            current.prev_node=newNode

    def remove (self, element):
        current=self.head
        while element != current.data:
            current=current.next_node
        current.next_node.prev_node=current.prev_node
        current.prev_node.next_node=current.next_node
        current=None

我尝试运行但失败了。谁能告诉我为什么？

Answer 1

查看您的 add 函数的逻辑，我发现了一些问题 -

一旦你添加了一个元素，即一旦你的 self.head 和 self.tail 不再 - None - ，你正在做一个 while 循环查找 add_obj 是否大于 current.data 。但是while循环写错了。假设，我们只在链表中放入了 1 个元素，我们试图添加一个大于 current 的数据， current 将变为 current.next_node ，当前为 None ，然后你再次尝试做同样的检查，这次你尝试访问 None 对象的 data 属性结果是 Error。您的删除代码也存在类似问题。
其次，在你的添加函数中，你只处理大于头部的元素，如果稍后你添加一个小于所有其他元素的对象，你必须将它添加到self.head ，但这种情况没有得到处理。
您没有处理当前大于列表中所有其他元素的元素的添加，在这种情况下，我认为您打算使 self.tail 成为最大值的元素，但你也没有这样做。

Answer 2

def add (self, add_obj):
        newNode=DLLNode(add_obj)
        current=self.head
        if current==None:
            self.head=self.tail=newNode
        else:
            if add_obj<current.data:
                self.head.prev_node=newNode
                newNode.next_node=self.head
                self.head=newNode
                self.head.prev_node=None
            else:
                while add_obj>current.data:
                    current=current.next_node
                if current != None:
                    newNode.next_node=current
                    newNode.prev_node=current.prev_node
                    current.prev_node.next_node=newNode
                    current.prev_node=newNode
                else:
                    self.tail.next_node=newNode
                    newNode.prev_node=self.tail
                    self.tail=newNode
                    self.tail.next_node=None

排序双向链表

Sorted Doubly Linked List

python

doubly-linked-list

sortedlist