如何不使用Iterator，基于数组实现List接口的指定方法？

这是《Java编程与数据结构导论》的练习24_01，需求是基于自定义的MyList<E>接口实现Collection接口中的addAll、removeAll、retainAll、toArray()和toArray(T[])方法，且禁止使用Iterator（在线课程系统不允许导入），教授建议通过数组来解决。

先贴出你当前的代码（已修正HTML转义字符）：

public interface MyList<E> extends java.util.Collection<E> {

    /** Add a new element at the specified index in this list */
    public void add(int index, E e);

    /** Return the element from this list at the specified index */
    public E get(int index);

    /** Return the index of the first matching element in this list.
     *  Return -1 if no match. */
    public int indexOf(Object e);

    /** Return the index of the last matching element in this list
     *  Return -1 if no match. */
    public int lastIndexOf(E e);

    /** Remove the element at the specified position in this list
     *  Shift any subsequent elements to the left.
     *  Return the element that was removed from the list. */
    public E remove(int index);

    /** Replace the element at the specified position in this list
     *  with the specified element and returns the new set. */
    public E set(int index, E e);

    @Override /** Add a new element at the end of this list */
    public default boolean add(E e) {
        add(size(), e);
        return true;
    }

    @Override /** Return true if this list contains no elements */
    public default boolean isEmpty() {
        return size() == 0;
    }

    @Override /** Remove the first occurrence of the element e 
     *  from this list. Shift any subsequent elements to the left.
     *  Return true if the element is removed. */
    public default boolean remove(Object e) {
        if (indexOf(e) >= 0) {
            remove(indexOf(e));
            return true;
        } else
            return false;
    }

    @Override
    public default boolean containsAll(Collection<?> c) {
        boolean contains = true;
        while(contains == true) {
            for(int i = 0; i < c.size(); i++) {
                if(indexOf() == -1) { // 错误：indexOf缺少参数
                    contains = false;
                }
            }
        }
        return contains;
    }

    @Override
    public default boolean addAll(Collection<? extends E> c) {
        // 未实现
    }

    @Override
    public default boolean removeAll(Collection<?> c) {
        Iterator<?> j = c.iterator(); // 禁用Iterator，不能用
        while(j.hasNext()) {
            if (indexOf(j.next()) >= 0) {
                remove(indexOf(j.next())); // 错误：j.next()被调用两次，会跳过元素
            }
        }
        return true;
    }

    @Override
    public default boolean retainAll(Collection<?> c) {
        Iterator<?> j = c.iterator(); // 禁用Iterator
        Object temp = j.next();
        while(j.hasNext()) {
            if(indexOf(temp) == -1) {
                remove(indexOf(temp));
            }
        }
        return true;
    }

    @Override
    public default Object[] toArray() {
        Object[] j = new Object[this.size()];
        for (int i = 0; i < this.size(); i++)
            j[i] = (Object) (this.get(i));
        if (size() > 0)
            return (E[]) temp; // 错误：temp未定义
        else
            return null; // 错误：空列表应返回空数组而非null
        return null;
    }

    @Override
    public default <T> T[] toArray(T[] array) {
        Object[] j = new Object[this.size()];
        for (int i = 0; i < this.size(); i++)
            j[i] = (Object) (this.get(i));
        if (size() > 0)
            return (T[]) temp; // 错误：temp未定义
        else
            return null; // 错误：空列表应返回空数组而非null
        return null;
    }
}

接下来逐个修正并实现这些方法，核心思路是利用数组遍历替代Iterator：

1. 修正containsAll方法 #

原代码存在参数缺失、循环逻辑错误的问题。我们可以调用c.toArray()将传入的Collection转为数组，遍历数组元素逐一检查是否存在于当前列表。

@Override
public default boolean containsAll(Collection<?> c) {
    // 将Collection转为数组，避免使用Iterator
    Object[] elements = c.toArray();
    for (Object e : elements) {
        if (indexOf(e) == -1) {
            return false; // 只要有一个元素不存在，直接返回false
        }
    }
    return true;
}

2. 实现addAll方法 #

将传入Collection的所有元素添加到当前列表，用数组遍历传入的元素，记录是否有元素被添加（只要添加成功至少一个，就返回true）。

@Override
public default boolean addAll(Collection<? extends E> c) {
    if (c.isEmpty()) {
        return false; // 没有元素添加，返回false
    }
    Object[] elements = c.toArray();
    boolean modified = false;
    for (Object obj : elements) {
        E e = (E) obj;
        add(e); // 调用已实现的add(E e)默认方法
        modified = true;
    }
    return modified;
}

3. 实现removeAll方法 #

移除当前列表中所有存在于传入Collection的元素，用数组遍历传入的Collection元素，调用已实现的remove(Object e)方法循环移除所有匹配项。

@Override
public default boolean removeAll(Collection<?> c) {
    if (c.isEmpty() || isEmpty()) {
        return false; // 无元素可移除，返回false
    }
    Object[] elements = c.toArray();
    boolean modified = false;
    for (Object e : elements) {
        // 循环移除所有匹配的元素（因为remove(Object e)只移除第一个）
        while (remove(e)) {
            modified = true;
        }
    }
    return modified;
}

4. 实现retainAll方法 #

保留当前列表中存在于传入Collection的元素，需要遍历当前列表的元素（用get(index)），检查是否不在传入的Collection中，若不在则移除。注意要从后往前遍历，避免移除元素导致索引偏移。

@Override
public default boolean retainAll(Collection<?> c) {
    if (isEmpty()) {
        return false;
    }
    boolean modified = false;
    // 从后往前遍历，避免移除元素后索引错乱
    for (int i = size() - 1; i >= 0; i--) {
        E element = get(i);
        if (!c.contains(element)) {
            remove(i);
            modified = true;
        }
    }
    return modified;
}

5. 实现toArray()方法 #

创建与当前列表大小一致的Object数组，遍历用get(i)填充元素，空列表返回空数组而非null。

@Override
public default Object[] toArray() {
    Object[] array = new Object[size()];
    for (int i = 0; i < size(); i++) {
        array[i] = get(i);
    }
    return array;
}

6. 实现toArray(T[] array)方法 #

需要处理两种情况：传入数组长度不足时，创建新的同类型数组；长度足够时，用传入的数组填充，超出部分设为null（符合Collection规范）。

@Override
public default <T> T[] toArray(T[] array) {
    if (array.length < size()) {
        // 传入数组长度不足，创建新的同类型数组
        array = (T[]) java.lang.reflect.Array.newInstance(array.getClass().getComponentType(), size());
    }
    // 填充元素
    for (int i = 0; i < size(); i++) {
        array[i] = (T) get(i);
    }
    // 若传入数组长度大于当前size，将超出位置设为null
    if (array.length > size()) {
        array[size()] = null;
    }
    return array;
}

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