过滤 DLL 中的节点

Question

这是我目前所拥有的，我想创建一个函数来删除双向链表中低于指定值或高于指定值的元素。

class DoublyLinkedList:

    class Node:
        """ Nodes in list """

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

    def __init__(self):
        self._header = self.Node(None, None, None)
        self._trailer = self.Node(None, None, None)
        self._header.next = self._trailer
        self._trailer.prev = self._header
        self._size = 0

    def append(self, element):

        :arg element: the value to add to this list
        
        new_node = self.Node(element, self._trailer.prev, self._trailer)
        self._trailer.prev.next = new_node
        self._trailer.prev = new_node
        self._size += 1

    def __len__(self):
        return self._size

    def __str__(self):

        # Python's list is used here to avoid string concatenation
        result = []

        current = self._header.next
        for i in range(len(self)):
            result.append(current.element)
            current = current.next

        return str(result)

    def remove(self, low, high):
        for element in self:
            try:
    
            if element.next < low:
                element.next = element.next.next
        
            elif element.next > high:
                element.next = element.next.next
        
            except Exception as e:
                print('low must be less than or equal to high')
        
        pass

^^ 这就是我到目前为止所尝试的 ^^ 这是我希望它工作的方式：我不确定如何让它过滤掉较高或较低的值

DoublyLinkedList.append(5)
DoublyLinkedList.append(7)
DoublyLinkedList.append(8)
DoublyLinkedList.append(3)
DoublyLinkedList.append(9)

[5, 7, 8, 3, 9]


DoublyLinkedList.remove(5,8)

its output should be:

[5, 7, 8]

Answer 1

您的代码中存在一些问题：

append 有一行应该是注释（以 # 开头）
for element in self: 将不起作用，因为 self 不可迭代。此外，当您计划从同一个集合中删除项目时，使用 for 循环遍历集合很少是一个好主意。最好使用您已经在 __str__ 方法中使用过的迭代形式。
element.next < low 比较两种不同的类型：.next 是一个节点，而 low 是一个数字。调用该循环变量 element 令人困惑，因为这也是节点属性的名称。你想要 current.next.element < low.
如果上述内容得到纠正，那么 try 块就没有理由触发异常，假设它与 low 和 high 的关系有关彼此。如果你想在 high > low 时输出一条消息，那么不要在循环中这样做，而是在开始循环之前测试那个条件。
当您删除一个节点时，您还应该减小列表大小。
您可以通过在一个表达式中使用一个 if 与 low 和 high 进行比较来避免代码重复，使用运算符链接
DoublyLinkedList 是 class，但列表应该是 class 的实例。所以你需要先创建那个实例，然后调用那个实例的方法，而不是 class.

这是对您的代码的更正：

class DoublyLinkedList:

    class Node:
        """ Nodes in list """

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

    def __init__(self):
        self._header = self.Node(None, None, None)
        self._trailer = self.Node(None, None, None)
        self._header.next = self._trailer
        self._trailer.prev = self._header
        self._size = 0

    def append(self, element):
        # :arg element: the value to add to this list
        new_node = self.Node(element, self._trailer.prev, self._trailer)
        self._trailer.prev.next = new_node
        self._trailer.prev = new_node
        self._size += 1

    def __len__(self):
        return self._size

    def __str__(self):
        result = []
        current = self._header.next
        for i in range(len(self)):
            result.append(current.element)
            current = current.next
        return str(result)

    def remove(self, low, high):
        # Perform the check before the loop
        if low > high:
            print('low must be less than or equal to high')
            return
        # Iterate the nodes like in __str__, but start one node earlier
        current = self._header
        for i in range(len(self)):
            # Don't compare the node, but its element.
            # Use chained comparison;
            if low <= current.next.element <= high:
                # Only move to next node when not removing
                current = current.next
            else:
                current.next = current.next.next
                self._size -= 1  # Also reduce size

# Should create an instance and work with that
lst = DoublyLinkedList()
lst.append(5)
lst.append(7)
lst.append(8)
lst.append(3)
lst.append(9)
print(lst)  # [5, 7, 8, 3, 9]
lst.remove(5,8)
print(lst)  # [5, 7, 8]

过滤 DLL 中的节点

Filtering nodes in a DLL

python

python-3.x

linked-list

doubly-linked-list