从链表中删除具有"sentinels"的节点

Question

我正在尝试根据CLRS书编写一个具有哨兵的链表。出于某种原因，我的删除函数删除了要删除的节点的 LL 块。附上我的代码。任何建议将不胜感激。

class Node():
    def __init__(self,v):
        self.value = v
        self.next = None
        self.prev = None
    def getValue(self):
        return self.value
    def changeValue(self,v):
        self.value = v
    def getNext(self):
        return self.next
    def getPrev(self):
        return self.prev
    def setNext(self,newNext):
        self.next = newNext
    def setPrev(self,newPrev):
        self.prev = newPrev
class List(Node):
    def __init__(self):
        self.nil = Node(None)
    def addNode(self,v):
        a = Node(v)
        a.setNext(self.nil.next)
        a.setPrev(self.nil)
        self.nil.next = a
    def length(self):
        count = 0
        a = self.nil
        while(a.next != None):
            count += 1
            a = a.getNext()
        return count
    def search(self,v):
        a = self.nil
        while(a.next != None):
            if (a.value == v):
                return True
            a = a.getNext()
        return False
    def remove(self,v):
        a = self.nil.next
        breakloop = 0
        while((a.next != None) and (breakloop == 0)):
            if (a.value == v):
                a.prev.next = a.next
                a.next.prev = a.prev
                breakloop = 1
            a = a.getNext()
    def printList(self):
        a = self.nil.next
        while(a.next != None):
            print(a.value)
            a =a.getNext()
        print(a.value)

a = List()
a.addNode(4)
a.addNode(7)
a.addNode(2)
a.addNode(6)
a.addNode(5)
a.addNode(8)
a.addNode(1)
a.addNode(14)
a.addNode(13)
a.addNode(17)
a.addNode(18)
a.printList()
a.remove(13)
a.printList()

输出将是
18 17 13 14 1 8 5 6 2 7 4
14 1 8 5 6 2 7 4

Answer 1

@tcaswell已经正确诊断了代码的问题：您没有在以前正确self.nil.next的节点上设置prev链接。但是，我认为他的解决方案并不理想。这是我的建议：

以下是该问题的直接解决方法：

def addNode(self, v):
    a = Node(v)
    a.setNext(self.nil.next)
    self.nil.next.setPrev(a) # this is the link that was previously missing
    a.setPrev(self.nil)
    self.nil.setNext(a)

但是，当列表为空时，这将无法正常工作，因为self.nil.next在开始时None。不过，我们可以通过在List构造函数中创建它时建立self.nil链接到自身来修复它：

def __init__(self):
    self.nil = Node(None)
    self.nil.next = self.nil.prev = self.nil # set up circular links!

现在，self.nil将始终有一个有效的节点，因为它是next和prev值。

您需要更改removeNode和printList循环以检查self.nil而不是None。

Answer 2

错误出在您的

addNode函数中，所有节点的.prev节点都self.nil

使用以下方法：

def addNode(self,v):
    a = Node(v)
    a.setNext(self.nil.next)
    if self.nil.next is not None:
        self.nil.next.setPrev(a)
    a.setPrev(self.nil)
    self.nil.next = a

将解决您的问题。 您可能希望将此逻辑放在setPrev和setNext函数中(以确保除末端之外的所有a始终a == a.next.prev和a == a.prev.next(。