Python循环双链表：实现removeAll函数删除所有匹配元素

本文提供了一个使用 Python 实现循环双链表的完整代码示例，重点介绍了 removeAll(CirSinglyList<T> pattern) 函数的实现，该函数用于删除链表中所有与给定模式匹配的元素。

代码实现pythonclass Node: def init(self, data): self.data = data self.prev = None self.next = None

class CirSinglyList: def init(self): self.head = None self.tail = None

def is_empty(self):        return self.head is None

def add(self, data):        new_node = Node(data)        if self.is_empty():            self.head = new_node            self.tail = new_node            new_node.next = new_node            new_node.prev = new_node        else:            new_node.prev = self.tail            new_node.next = self.head            self.head.prev = new_node            self.tail.next = new_node            self.tail = new_node

def remove(self, data):        if self.is_empty():            return

    current = self.head        while current.data != data:            current = current.next            if current == self.head:                return

    if current.prev == current:            self.head = None            self.tail = None        else:            current.prev.next = current.next            current.next.prev = current.prev            if current == self.head:                self.head = current.next            if current == self.tail:                self.tail = current.prev

def removeAll(self, pattern):        if self.is_empty():            return

    current = self.head        while True:            if current.data == pattern:                self.remove(current.data)                # 注意：删除节点后，需要重新获取头节点                current = self.head                 if current is None: # 处理链表为空的情况                    break            else:                current = current.next                if current == self.head:                    break

def display(self):        if self.is_empty():            return

    current = self.head        while True:            print(current.data, end=' ')            current = current.next            if current == self.head:                break

测试代码if name == 'main': myList = CirSinglyList() myList.add(1) myList.add(2) myList.add(3) myList.add(2) myList.add(4) myList.add(2)

print('原始链表：')    myList.display()

pattern = 2    myList.removeAll(pattern)

print('

移除所有匹配项后的链表：') myList.display()

代码解释

Node 类表示循环双链表中的节点，包含数据域 data 以及指向前驱节点和后继节点的指针 prev 和 next。* CirSinglyList 类表示循环双链表，包含头节点 head 和尾节点 tail。 * is_empty()：判断链表是否为空。 * add(data)：在链表尾部添加一个新节点。 * remove(data)：删除链表中第一个值为 data 的节点。 * removeAll(pattern)：删除链表中所有值为 pattern 的节点。 * 使用循环遍历链表，找到匹配的节点就调用 remove() 方法删除。 * 注意：在删除节点后，需要重新获取头节点，因为头节点可能已经改变。 * display()：打印链表的所有节点值。

测试用例

在 main 函数中，我们创建了一个循环双链表，并添加了一些元素。然后调用 removeAll 函数删除所有值为 2 的节点，最后打印修改后的链表。

输出：

原始链表：1 2 3 2 4 2 移除所有匹配项后的链表：1 3 4

总结

本文提供了一个 Python 实现的循环双链表 removeAll 函数的完整代码示例，并进行了详细的代码解释和测试用例分析。希望对您理解循环双链表以及 removeAll 函数的实现有所帮助。