Java循环双链表removeAll()方法详解（附完整代码）

Java循环双链表removeAll()方法详解

本文介绍如何使用Java实现循环双链表，并重点讲解removeAll(T pattern)方法的实现。该方法用于移除链表中所有与给定模式匹配的元素。

代码实现

以下是完整的Java代码，包括Node类和CirSinglyList类，以及一个包含测试用例的main函数：

public class Node<T> {
    public T data;
    public Node<T> prev;
    public Node<T> next;

    public Node(T data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class CirSinglyList<T> {
    private Node<T> head;
    private Node<T> tail;

    public CirSinglyList() {
        this.head = null;
        this.tail = null;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
            newNode.next = newNode;
            newNode.prev = newNode;
        } else {
            newNode.prev = tail;
            newNode.next = head;
            head.prev = newNode;
            tail.next = newNode;
            tail = newNode;
        }
    }

    public void remove(T data) {
        if (isEmpty()) {
            return;
        }

        Node<T> current = head;
        while (!current.data.equals(data)) {
            current = current.next;
            if (current == head) {
                return;
            }
        }

        if (current.prev == current) {
            head = null;
            tail = null;
        } else {
            current.prev.next = current.next;
            current.next.prev = current.prev;
            if (current == head) {
                head = current.next;
            }
            if (current == tail) {
                tail = current.prev;
            }
        }
    }

    public void removeAll(T pattern) {
        if (isEmpty()) {
            return;
        }

        Node<T> current = head;
        do {
            if (current.data.equals(pattern)) {
                remove(current.data);
            }
            current = current.next;
        } while (current != head);
    }

    public void display() {
        if (isEmpty()) {
            return;
        }

        Node<T> current = head;
        do {
            System.out.print(current.data + ' ');
            current = current.next;
        } while (current != head);
    }

    public static void main(String[] args) {
        CirSinglyList<Integer> myList = new CirSinglyList<>();
        myList.add(1);
        myList.add(2);
        myList.add(3);
        myList.add(2);
        myList.add(4);
        myList.add(2);

        System.out.println('原始链表：');
        myList.display();

        int pattern = 2;
        myList.removeAll(pattern);

        System.out.println('\n移除所有匹配项后的链表：');
        myList.display();
    }
}

代码解释

1. Node类: 表示循环双链表中的节点，包含数据域data和前后指针prev、next。
2. CirSinglyList类:
   • head和tail：分别指向链表头节点和尾节点。
   • isEmpty()：判断链表是否为空。
   • add(T data)：在链表尾部添加新节点。
   • remove(T data)：移除链表中第一个值为data的节点。
   • removeAll(T pattern)：移除链表中所有值为pattern的节点。
     • 使用循环遍历链表。
     • 使用current.data.equals(pattern)判断当前节点是否匹配模式。
     • 调用remove(current.data)移除匹配的节点。
     • 循环结束后，所有匹配的节点都被移除。
   • display()：打印链表内容。
3. main函数:
   • 创建一个CirSinglyList对象，添加示例数据。
   • 调用removeAll(2)移除所有值为2的节点。
   • 打印修改后的链表内容，验证removeAll()方法的正确性。

总结

本文介绍了Java循环双链表的removeAll()方法的实现，并提供了完整的代码示例。希望本文能帮助您理解循环双链表的概念和操作，并在实际项目中灵活应用。