面试题：Java ArrayList迭代器的自定义实现及优化

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class CustomArrayListIterator<E> {
    private final ArrayList<E> list;
    private int cursor; // 下一个要返回元素的索引
    private int lastRet = -1; // 上一个返回元素的索引
    private boolean forward; // 当前遍历方向，true为正向，false为反向

    public CustomArrayListIterator(ArrayList<E> list) {
        this.list = list;
        this.cursor = 0;
        this.forward = true;
    }

    public boolean hasNext() {
        return forward? cursor < list.size() : cursor >= 0;
    }

    public E next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        lastRet = forward? cursor++ : cursor--;
        return list.get(lastRet);
    }

    public boolean hasPrevious() {
        return forward? cursor > 0 : cursor < list.size();
    }

    public E previous() {
        if (!hasPrevious()) {
            throw new NoSuchElementException();
        }
        lastRet = forward? --cursor : cursor++;
        return list.get(lastRet);
    }

    public void remove() {
        if (lastRet < 0) {
            throw new IllegalStateException();
        }
        list.remove(lastRet);
        if (forward) {
            cursor = Math.max(0, cursor - 1);
        } else {
            cursor = Math.min(list.size(), cursor + 1);
        }
        lastRet = -1;
    }
}

删除操作时间复杂度分析

时间复杂度：remove 方法中调用了 ArrayList 的 remove 方法，ArrayList 删除元素的时间复杂度为 $O(n)$，因为在删除元素后，后续元素需要向前移动。所以这里 remove 操作的时间复杂度也是 $O(n)$，其中 $n$ 是 ArrayList 中元素的个数。

大规模数据情况下的优化

使用链表结构：ArrayList 基于数组实现，删除元素时需要移动后续元素。而链表结构在删除元素时，只需要修改指针，时间复杂度为 $O(1)$。可以考虑将底层数据结构改为双向链表，如 LinkedList，这样删除操作的时间复杂度将大大降低。
批量删除：如果需要删除多个元素，可以先记录要删除的元素索引，最后批量处理，减少数据移动的次数。例如，先将所有要删除的元素索引存入一个 List 中，然后从后往前遍历这个 List 进行删除操作，这样可以避免每次删除后索引的变化对后续删除操作的影响。
使用 CopyOnWriteArrayList：在多线程环境下，CopyOnWriteArrayList 可以在遍历的同时允许其他线程进行写操作，通过在写操作时复制一份新的数组来实现，读操作则基于原数组，从而实现读写分离，提高并发性能。但这种方式会增加内存消耗。

面试题：Java ArrayList迭代器的自定义实现及优化

知识考点

面试题答案

删除操作时间复杂度分析

大规模数据情况下的优化