java - 我应该使用哪种 Java 集合类型？

Question

我正在尝试用 Java 创建一个“有限列表”。如果我添加新条目，它应该删除旧条目。

例如如果列表大小为 3，并且我添加了第 4 个项目，它应该删除第一个项目。目前我在 ArrayList 中使用 remove(0) 解决了这个问题，但我听说 ArrayList 非常慢。

有没有更快的方法来解决这个问题？我当前的代码是:

public class LimitedList<T> extends ArrayList<T> {
    private int maximum;

    public LimitedList(int maximum) {
        this.maximum = maximum;
    }

    @Override
    public boolean add(T t) {
        boolean r = super.add(t);
        while (size() > maximum) {
            remove(0);
        }
        return r;
    }

}

Answer 1

but I heard ArrayList's are very slow.

某些操作对于 ArrayList 很慢s others 用于其他 Collection 。这是因为 ArrayList在窗帘后面使用一个数组，对于头部的删除操作，它必须将所有元素向左移动一个。因此，就大哦而言，对于 ArrayList，从头部移除是 O(n) LinkedList 的 O(1)

如果你只想在集合的尾部添加项目并删除头部的元素，我建议你使用 LinkedList :

public class LimitedList<T> extends LinkedList<T> {

    private int maximum;

    public LimitedList(int maximum) {
        this.maximum = maximum;
    }

    @Override
    public boolean add(T t) {
        boolean r = super.add(t);
        int n = this.size();
        while (n > maximum) {
            this.removeFirst();
            n--;
        }
        return r;
    }

}

来自 @JBNizet 的重要说明是你应该继承自 ArrayList或 LinkedList直接，但实现一个 Collection<T> ，类似于:

public class LimitedList<T> implements Collection<T> {

    private final LinkedList<T> list;
    private int maximum;

    public LimitedList(int maximum) {
        this.list = new LinkedList<T>();
        this.maximum = maximum;
    }

    @Override
    public boolean add(T t) {
        boolean r = this.list.add(t);
        int n = this.list.size();
        while (n > maximum) {
            this.list.removeFirst();
            n--;
        }
        return r;
    }

    //implement other Collection methods...

}