Florian Florian - 5 months ago 9
Java Question

Which Java collection type should I use?

I'm trying to create a "Limited List" in Java. It should remove old entries if I add new entries.

e.g. If the list size is 3, and I add the 4rd item, it should remove the 1st item. Currently I solved this using

remove(0)
in a
ArrayList
, but I heard
ArrayList
s are very slow.

Is there a faster way to solve this? My current code is:

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

but I heard ArrayList's are very slow.

Some operations are slow for ArrayLists others for other collections. This is because an ArrayList uses an array behind the curtains, and for a remove operation in the head, it has to shift all the elements one to the left. Therefore in terms of big oh, removing from the head is O(n) for ArrayLists where it is O(1) for LinkedLists.

If you only want to add items in the tail of the collection and remove elements in the head, I propose you use a 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;
    }

}

An important note from @JBNizet is that you should inherit from ArrayList or LinkedList directly, but implement a Collection<T>, something like:

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...

}
Comments