自定义链表元素批量删除：removeAll 方法的深度解析-java教程-PHP中文网

自定义链表元素批量删除：removeall 方法的深度解析

本教程详细阐述了如何在自定义链表中高效实现`removeAll`功能，以删除所有匹配特定元素的节点。文章强调了Java中`equals()`方法与`==`操作符在对象比较上的根本区别，并提供了逐步的实现逻辑，涵盖了链表头、尾和中间节点的删除场景，确保链表状态（如头指针、尾指针和元素计数）的准确维护，并附带了`equals()`和`hashCode()`方法的最佳实践。

自定义链表中的元素批量删除挑战

在Java中实现自定义链表时，删除特定元素的所有实例是一个常见的需求。与删除单个元素不同，批量删除要求我们遍历整个链表，识别并移除所有与目标元素匹配的节点。这个过程不仅需要精确地更新节点之间的链接，还要正确维护链表的头部（list）、尾部（last）以及元素计数（count）等关键属性。

一个常见的陷阱是对Java对象比较的理解不足，尤其是在使用==操作符与equals()方法时。如果不对这些细节进行妥善处理，可能会导致部分元素未被删除、链表结构损坏或程序行为异常。

理解Java中的对象比较：equals()与==

在Java中，比较两个对象是否“相等”有两种主要方式：

== 操作符： ==操作符用于比较两个变量的值。对于基本数据类型，它比较的是实际的数值。然而，对于对象引用类型，==比较的是这两个引用是否指向内存中的同一个对象实例。换句话说，它检查的是两个引用变量是否存储了相同的内存地址。因此，即使两个对象的内容完全相同，如果它们是不同的实例，==也会返回false。

equals() 方法： equals()方法是Object类中定义的一个方法，用于判断两个对象在逻辑上是否相等。默认情况下，Object类的equals()方法行为与==操作符相同，即比较对象的内存地址。然而，对于自定义类（如本例中的employee），我们通常需要根据对象的属性值来判断其逻辑相等性。

重要提示： 如果您的链表存储的是自定义对象（例如employee），并且您希望根据对象的内容（例如courseName）来判断是否需要删除，那么必须在employee类中重写equals()方法。否则，即使您传入一个内容相同的employee对象，clear方法也无法正确识别并删除链表中的匹配项。

示例：employee类中equals()和hashCode()的重写

import java.util.Objects;

public class employee {
    private String number;
    private String name;
    private int years;
    private String courseName;

    public employee(String number, String name, int years, String courseName) {
        this.number = number;
        this.name = name;
        this.years = years;
        this.courseName = courseName;
    }

    // Getter methods (omitted for brevity)
    public String getCourseName() {
        return courseName;
    }

    // 假设我们根据 courseName 来判断相等性，或者根据所有字段
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        employee employee = (employee) o;
        // 根据需求选择比较字段。例如，如果只根据 courseName 判断相等
        // return Objects.equals(courseName, employee.courseName);
        // 如果根据所有字段判断相等
        return years == employee.years &&
               Objects.equals(number, employee.number) &&
               Objects.equals(name, employee.name) &&
               Objects.equals(courseName, employee.courseName);
    }

    @Override
    public int hashCode() {
        // hashCode 必须与 equals 保持一致
        return Objects.hash(number, name, years, courseName);
        // 如果 equals 只比较 courseName，则 hashCode 也应只基于 courseName
        // return Objects.hash(courseName);
    }

    @Override
    public String toString() {
        return "Employee{" +
               "number='" + number + '\'' +
               ", name='" + name + '\'' +
               ", years=" + years +
               ", courseName='" + courseName + '\'' +
               '}';
    }
}

登录后复制

在上述equals方法中，您可以根据实际业务逻辑选择比较一个或多个字段。但无论如何，一旦重写了equals，就必须同时重写hashCode以保持两者的一致性。

实现removeAll（或clear）方法

为了从自定义链表中删除所有匹配的元素，我们需要一个迭代过程，同时跟踪当前节点和前一个节点，以便在删除时正确地重新链接链表。

以下是LinkedList类中clear方法的优化实现，它能够删除所有与给定元素逻辑相等的节点：

稿定AI设计

AI自动去水印、背景消除、批量抠人像工具

查看详情

public class LinkedList<T> implements LinkedListADT<T> {

     private int count;  // the current number of elements in the list
     private LinearNode<T> list; //pointer to the first element (head)
     private LinearNode<T> last; //pointer to the last element (tail)

     // ... (Constructor, add, remove methods as provided, or optimized) ...

     /**
      * 从链表中删除所有与指定元素逻辑相等的实例。
      *
      * @param element 要删除的目标元素。
      * @return 实际删除的元素数量。
      */
     public long clear(T element) {
         long result = 0L; // 记录删除的元素数量

         LinearNode<T> current = this.list; // 当前遍历的节点
         LinearNode<T> previous = null;    // 当前节点的前一个节点

         while (current != null) {
             // 使用 equals() 方法进行逻辑比较
             if (current.getElement().equals(element)) {
                 // 匹配成功，准备删除当前节点
                 if (previous != null) {
                     // 情况1：删除的是中间节点或尾节点
                     previous.setNext(current.getNext());
                     // 如果删除的是原链表的最后一个节点，需要更新 last 指针
                     if (current.getNext() == null) {
                         this.last = previous;
                     }
                 } else {
                     // 情况2：删除的是头节点
                     this.list = current.getNext();
                     // 如果链表因此变空，需要更新 last 指针
                     if (this.list == null) {
                         this.last = null;
                     }
                 }
                 this.count--; // 元素计数减一
                 result++;     // 删除数量加一

                 // 注意：删除后 current 应该指向下一个待检查的节点，
                 // 由于 previous.setNext(current.getNext()) 已经处理了链接，
                 // 此时 current 实际上已经从链表中“移除”，
                 // 下一次循环中 current 应该指向 previous 的新 next。
                 // 但为了逻辑清晰，我们让 current 继续前进到它“原本”的下一个节点
                 // 这样在下一次循环开始时，current 就指向了正确的位置。
                 // 实际上，如果删除的是头节点，current会直接跳到新的头节点。
                 // 如果删除的是中间节点，current会跳过被删除的节点。
                 // 这里的处理方式是让 current 保持指向被删除节点的“下一个”，
                 // 这样在循环末尾的 current = current.getNext() 之前，
                 // current 实际上是已经从链表中移除的那个节点。
                 // 更简洁的做法是：如果删除了节点，current 不应该再前进，
                 // 因为 previous.next 已经指向了新的 current。
                 // 但是为了保持循环结构统一，我们可以在这里直接更新 current。
                 // 这里的实现是让 current 保持指向被删除节点的下一个，
                 // 这样在循环的最后一步 current = current.getNext() 会再次更新 current。
                 // 更好的方式是：如果删除了节点，current应该指向 previous.getNext()。
                 // 让我们调整一下逻辑，使之更清晰：
                 // 如果删除了节点，current 不应该在这次迭代结束时通过 current.getNext() 移动，
                 // 因为 previous.next 已经指向了新的 current。
                 // 修正后的逻辑如下：
                 // current = (previous == null) ? this.list : previous.getNext();
                 // 这样，如果删除了节点，current会指向被删除节点后面的那个节点，
                 // 或者在删除头节点时指向新的头节点。
                 // 原始答案的写法是：在删除后，current 仍然指向被删除的节点，
                 // 然后在循环的最后一步 current = current.getNext() 时，
                 // current 才会跳到下一个节点。这会导致在某些情况下，
                 // 如果连续有多个相同元素，current 可能会跳过一个本应被删除的节点。
                 // 让我们采用更健壮的双指针方法：
                 // 如果删除了节点，我们不移动 previous，因为新的 current 已经由 previous.setNext() 确定。
                 // 如果没有删除，才移动 previous。
                 // 让我们按照答案提供的逻辑来解释，并指出其微妙之处。
                 // 答案中的 current = current.getNext(); 实际上是让 current 指向了被删除节点的下一个，
                 // 然后在下一次循环开始时，这个新的 current 会被检查。
                 // 这种写法是正确的，因为它确保了所有节点都会被检查。
             } else {
                 // 不匹配，移动 previous 指针
                 previous = current;
             }
             current = current.getNext(); // 移动 current 指针到下一个节点
         }
         return result;
     }

     // ... (Other methods like size(), toString() etc.) ...
}

登录后复制

代码解析与注意事项

上述clear方法通过双指针（current和previous）遍历链表，逐一检查每个节点。

初始化：
- result：用于记录成功删除的元素数量。
- current：初始化为链表的头节点（this.list）。
- previous：初始化为null，因为它在遍历开始时没有前一个节点。
循环遍历： while (current != null)确保我们遍历到链表的末尾。
元素匹配： if (current.getElement().equals(element))是核心判断。这里必须使用equals()方法进行逻辑比较。
删除逻辑：
- 删除中间或尾节点 (previous != null)： previous.setNext(current.getNext()); 这一步将previous节点直接链接到current的下一个节点，从而将current节点从链表中移除。如果current是链表的最后一个节点（即current.getNext() == null），那么在删除它之后，previous就成了新的尾节点，因此需要更新this.last = previous;。
- 删除头节点 (previous == null)： this.list = current.getNext(); 这一步将链表的头指针（this.list）直接指向current的下一个节点，有效地移除了原头节点。如果链表因此变为空（即this.list变为null），那么尾指针this.last也必须设为null。
更新状态：
- this.count--;：每删除一个节点，链表中的元素计数就减一。
- result++;：增加删除元素的计数。
指针前进：
- 不匹配时：previous = current; 将previous指针移动到当前的current位置。
- 无论是否匹配：current = current.getNext(); 将current指针移动到下一个待检查的节点。这种方式确保了即使当前节点被删除，我们也能继续检查其后面的节点。

关键注意事项：

equals()方法的重要性：再次强调，确保T类型（如employee）正确重写了equals()和hashCode()方法，否则clear方法将无法按预期工作。
头尾指针的维护：在删除头节点或尾节点时，必须精确更新this.list和this.last指针，以保持链表的完整性。
空链表处理：当链表中的所有元素都被删除时，this.list和this.last都应设为null，且count应为0。
返回删除数量：返回删除元素的数量是一个良好的实践，可以提供操作结果的反馈。