Bag类remove()方法实现咨询：给定如下Java Bag类代码

我帮你完善了这个基于链表的Bag类，补充了缺失的方法实现，并且添加了两种常用的remove()方法：一种是移除背包中的任意一个元素（默认取链表首节点，操作最高效），另一种是移除指定的目标元素。

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private int N; // 背包中的元素数量
    private Node<Item> first; // 背包的起始节点

    // 辅助链表类
    private class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    /**
     * 初始化一个空背包。
     */
    public Bag() {
        first = null;
        N = 0;
    }

    /**
     * 判断该背包是否为空？
     * @return 若背包为空则返回true，否则返回false
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 返回背包中的元素数量
     * @return 元素总数
     */
    public int size() {
        return N;
    }

    /**
     * 向背包中添加一个元素
     * @param item 要添加的元素
     */
    public void add(Item item) {
        Node<Item> oldFirst = first;
        first = new Node<>();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    /**
     * 移除背包中的任意一个元素（这里选择移除链表首节点，时间复杂度O(1)）
     * @return 被移除的元素
     * @throws NoSuchElementException 如果背包为空时调用此方法
     */
    public Item remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Bag is empty");
        }
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    /**
     * 移除背包中第一个匹配到的指定元素
     * @param target 要移除的目标元素
     * @return 若成功移除则返回true，若背包中无此元素则返回false
     */
    public boolean remove(Item target) {
        if (isEmpty()) {
            return false;
        }

        // 处理首节点就是目标元素的情况
        if (first.item.equals(target)) {
            first = first.next;
            N--;
            return true;
        }

        // 遍历链表查找目标元素
        Node<Item> current = first;
        while (current.next != null) {
            if (current.next.item.equals(target)) {
                current.next = current.next.next;
                N--;
                return true;
            }
            current = current.next;
        }

        // 没找到目标元素
        return false;
    }

    /**
     * 返回背包的迭代器，支持遍历所有元素
     */
    @Override
    public Iterator<Item> iterator() {
        return new BagIterator();
    }

    // 内部迭代器类
    private class BagIterator implements Iterator<Item> {
        private Node<Item> current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

关键方法说明 #

remove()（无参版本） #

• 这个版本利用链表的特性，直接移除首节点，操作效率是O(1)，非常高效。
• 因为背包是无序的，所以移除任意元素都符合背包的设计逻辑，不需要关心顺序。
• 当背包为空时，会抛出NoSuchElementException，符合Java集合类的异常规范。

remove(Item target)（指定元素版本） #

• 这个版本会遍历链表，找到第一个匹配的元素并移除，时间复杂度是O(N)（最坏情况需要遍历整个链表）。
• 注意这里使用equals()方法比较元素，所以如果是自定义类，需要确保重写了equals()方法才能正确匹配。
• 如果找不到目标元素，会返回false，不会抛出异常。

内容的提问来源于stack exchange，提问作者efedoganay