如何在双向链表中删除 - Python？

Question

我想在Python中创建一个双向链表。但是 rem = remove 给我带来了问题。我可以删除第一个元素，但我无法删除中间或最后的元素。

class节点：

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

class 列表DL:

def __init__(self):
    self.__head = None  
    self.__tail = None  
    self.__size = 0  

def rem(self, item):
    if self.__head is None:
        print("The list is empty")
        return
    if self.__head.next is None:
        if self.__head.data == item:
            self.__head = None
        else:
            print("Item not found")
        return

    if self.__head.data == item:
        self.__head = self.__head.next
        self.__head.prev = None
        return

    n = self.__head
    while n.next is not None:
        if n.data == item:
            break
        n = n.next
    if n.next is not None:
        n.prev.next = n.next
        n.next.prev = n.prev
    else:
        if n.data == item:
            n.prev.next = None
        else:
            print("Item is not present")

Answer 1

您的 rem 方法中至少有两个问题：

它从不更新 self.__tail。当尾节点是具有要删除的数据的节点时，它应该这样做。
只删除第一个有值的节点。如果打算删除具有该值的 all 个节点，那么您需要继续遍历列表以找到其他出现的节点。

你可以这样写：

    def rem(self, item):
        n = self.__head
        while n is not None:
            nxt = n.next
            if n.data == item:
                if n.prev:
                    n.prev.next = n.next
                else:
                    self.__head= n.next
                if n.next:
                    n.next.prev = n.prev
                else:
                    self.__tail = n.prev
            n = nxt

如何在双向链表中删除 - Python？

How to remove in a doubly linked list - Python?

python

doubly-linked-list