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

Question

一段时间以来，我一直在尝试在 Python 中创建双向链表，但在使用 LinkedList 类中的一些方法时遇到了问题。我希望我的 removeFront 和 removeRear 方法返回被删除的值，但我无法让它工作。使用测试列表，如果我将某个值 x 输入到节点并尝试将其删除，则不会返回 x。

我相信删除一个节点的想法是通过将它的下一个节点与其前一个节点连接起来，将其从列表中删除，但我觉得我在这方面的尝试存在根本性的缺陷。

我也在尝试实现 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

下面是带有注释的 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，你需要考虑三种不同的情况:

• 正在删除前面
• 正在删除后部
• 正在删除 front 和 rear 之间的节点

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