删除 Python 双链表中的节点时遇到问题

Question

我已经尝试在 Python 中创建一个双链表一段时间了，但是在我的 LinkedList class 中使用一些方法时遇到了问题。我希望我的 removeFront 和 removeRear 方法能够 return 删除的值，但我无法让它工作。对于测试列表，如果我在节点中输入一些值 x 并尝试将其删除，则 x 不是 returned.

我认为删除节点的想法是通过将下一个节点与其前一个节点连接起来，将其从列表中删除，但感觉我的尝试存在根本性的缺陷。

我也在尝试实现 pop 方法（删除列表中的特定元素）但我不确定从哪里开始。任何能使我朝着正确方向前进的建议都将不胜感激。谢谢。

class Node:

    def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None

class LinkedList:

    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        return self.front is None and self.rear is None

    def addFront(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
            self.rear = self.front
            self.front.prev = None
            self.rear.next = None
        else:
            self.front.prev = new_node
            new_node.next = self.front
            self.front = new_node
            self.front.prev = None

    def addRear(self, data):
        new_node = Node(data)
        if self.front is None:
            self.rear = new_node
            self.front = self.rear
            self.front.prev = None
            self.rear.next = None
        else:
            self.rear.next = new_node
            new_node.prev = self.rear
            self.rear = new_node
            self.rear.next = None

    def removeFront(self):
        if self.isEmpty():
            return None
        else:
            removed = self.front
            self.front.prev = self.front
            self.front.prev.next = None
            return removed

    def removeRear(self):
        if self.isEmpty():
            return None
        else:
            removed = self.rear
            self.rear.prev = self.rear
            self.rear.prev.next = None
            return removed

    def pop(self, index):
        # TODO: How to implement?
        pass

    def size(self):
        current = self.front
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

Answer 1

快速代码审查：

Node.__init__() 正确。
LinkedList.__init__() 正确。
LinkedList.isEmpty() 正确。
LinkedList.size() 正确。

以下是如何正确实施 LinkedList.removeFront()：

    def removeFront(self):
        if self.isEmpty():
            return None
        else:
            removed = self.front.data
            self.front = self.front.next
            if self.front is None:  # List size was 1
                self.rear = None
            else:
                self.front.prev = None
            return removed

我将 removeRear() 的实现作为练习留给您。逻辑对称于removeFront().

LinkedList.addFront()是正确的，但可以简化：

    def addFront(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
            self.rear = new_node
            #self.front.prev = None  # Already None
            #self.rear.next  = None  # Already None
        else:
            self.front.prev = new_node
            new_node.next = self.front
            self.front = new_node
            #self.front.prev = None  # Already None

你的LinkedList.addRear()是正确的，但可以用同样的方式简化。

您询问了如何实施 LinkedList.pop()。这将是一个棘手的问题。你必须考虑多种情况：

如果列表只有一个元素怎么办？
如果要删除的节点在前面怎么办？
如果要删除的节点在后面怎么办？
如果要删除的节点严格在中间怎么办？

Answer 2

这是 removeFront 的实现，带有注释：

def removeFront(self):
    if self.isEmpty():
        return None

    # Store data so that it can be returned
    data = self.front.data
    if self.front == self.rear:
        # List contains one item, set front & rear to initial state
        self.front = self.rear = None
    else:
        # More than one item
        self.front = self.front.next    # Set front to point next item
        self.front.prev = None          # Front doesn't have previous item

    return data

removeRear 完全符合相同的逻辑。

为了实施pop，您需要考虑三种不同的情况：

前面正在删除
后面正在删除
正在删除前后节点

无论是什么情况，您仍然需要找到要删除的正确节点。您可以在列表中前进时循环执行此操作。找到正确的节点后，您可以使用 removeFront 或 removeRear 以防它是第一个或最后一个节点。如果节点介于两者之间，则需要将其从上一个节点和下一个节点剪切下来，然后将剩余的节点连接在一起。

删除 Python 双链表中的节点时遇到问题

Trouble with removing nodes in Python double linked list

python

algorithm

linked-list

doubly-linked-list