Java自定义链表如何高效移除所有指定元素

在Java开发中，自定义链表是基础数据结构的重要组成部分，经常会遇到需要移除链表中所有指定元素的场景。如果采用普通的遍历删除方式，很容易因为指针移动问题导致元素遗漏，或者多次遍历造成性能浪费。下面我们将从链表结构设计开始，逐步讲解高效移除所有指定元素的实现方法。

自定义链表的基础结构设计

首先我们需要先定义一个简单的单向链表结构，包含节点类和链表类，节点类存储当前元素值和下一个节点的引用，链表类维护头节点和链表长度信息。

// 链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 自定义链表类
class MyLinkedList {
    ListNode head;
    int size;

    // 初始化链表
    public MyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 向链表尾部添加元素
    public void add(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
        size++;
    }

    // 打印链表元素
    public void printList() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

低效移除方式的常见问题

很多开发者初次实现移除所有指定元素时，会采用下面的遍历方式，这种方式存在明显的问题：

// 低效的移除实现，存在遗漏问题
public void removeAllBad(int target) {
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == target) {
            // 这里直接操作cur的next，会导致下一个节点被跳过
            if (cur == head) {
                head = head.next;
                cur = head;
            } else {
                // 缺少前驱节点引用，无法正确删除非头节点
                cur = cur.next;
            }
        } else {
            cur = cur.next;
        }
    }
}

这种写法的问题在于，删除节点时如果没有记录前驱节点，很容易出现指针混乱，而且如果连续两个节点都是目标元素，第二个元素会被直接跳过，导致删除不彻底。

高效移除所有指定元素的实现

高效实现的核心思路是引入虚拟头节点，统一头节点和非头节点的删除逻辑，同时只遍历一次链表，时间复杂度为O(n)，空间复杂度为O(1)。

// 高效移除所有指定元素的实现
public void removeAll(int target) {
    // 创建虚拟头节点，指向原头节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    ListNode cur = head;

    while (cur != null) {
        if (cur.val == target) {
            // 删除当前节点，前驱节点的next指向当前节点的下一个节点
            pre.next = cur.next;
            size--;
        } else {
            // 当前节点不需要删除，前驱节点后移
            pre = cur;
        }
        // 当前节点始终后移
        cur = cur.next;
    }
    // 更新头节点为虚拟头节点的下一个节点
    head = dummy.next;
}

实现逻辑解析

• 虚拟头节点dummy的作用是统一所有节点的删除逻辑，不需要单独处理头节点的特殊情况
• pre指针记录当前节点的前驱节点，当需要删除当前节点时，直接修改pre.next即可
• 无论当前节点是否需要删除，cur指针都向后移动，避免遗漏连续的目标元素
• 遍历完成后，更新链表的头节点为dummy.next，避免原头节点被删除后头节点引用失效

完整测试示例

下面是完整的测试代码，验证移除功能的正确性：

public class Main {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        // 添加测试元素，包含连续的目标元素
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(4);

        System.out.println("移除前链表元素：");
        list.printList();

        // 移除所有值为2的元素
        list.removeAll(2);

        System.out.println("移除后链表元素：");
        list.printList();
        System.out.println("当前链表长度：" + list.size);
    }
}

运行上述代码，输出结果如下：

移除前链表元素：
1 2 2 3 2 4 
移除后链表元素：
1 3 4 
当前链表长度：3

性能对比与总结

我们对比两种实现方式的性能：

通过虚拟头节点的方式实现自定义链表移除所有指定元素，既保证了逻辑的正确性，也实现了最优的时间复杂度，是实际开发中的推荐实现方案。开发者在实际使用时，可以根据链表的类型（单向/双向）调整指针的记录方式，核心思路都是统一删除逻辑，避免指针操作出错。

Java自定义链表移除指定元素链表操作修改时间：2026-05-25 22:00:20