List with max elements

Question

I would like to create a list in java that while adding new element, will check if limit was reached. If it was, delete oldest element.

I was thinking about making child of ArrayList and overriding add(Object). In there i would make that:

if(size() + 1 > MAX)
    remove(get(0));
super.add(newObject);

Any better way?

This is not a good idea. Removing the first element of an `ArrayList` causes all other elements to be shifted (which takes `O(n)` time). You should use a circular array instead. — Vincent van der Weele, Sep 23 '13 at 11:49
In addition to jazzbassrob's answer this [article](http://en.wikipedia.org/wiki/Least_recently_used#Least_Recently_Used) might be of interest. see also this [SO question](http://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java-6) — A4L, Sep 23 '13 at 11:55
Like others suggested, use a circular array. But as a general rule, I prefer composition over inheritance, which allows the decorator pattern. So if I wanted to use a list, I would rather make a decorator class for the list which enforces maximum size (and thus allows the user of the decorator to choose between ArrayList and LinkedList or even other lists) rather than make a subclass of ArrayList or LinkedList. — RokL, Sep 23 '13 at 12:29

score 5 · Accepted Answer · answered Sep 23 '13 at 11:50

5

There are probably a number of solutions to this, but I think that yours is a suitable approach if you make one change: your underlying implementation class should be a LinkedList, not an ArrayList. The reason is that when you call remove on an ArrayList every element after the removed value must be shifted up (making remove(0) the very worst case!). However this is not a problem for a LinkedList.

answered Sep 23 '13 at 11:50

devrobf

6,973
2
32
46

But there isnt anything like that already done in most known librarys like Javolution or Trove right? That a lot for the tip :) – user2618929 Sep 23 '13 at 11:53
1

@user2618929: see http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/queue/CircularFifoQueue.html – jlordo Sep 23 '13 at 12:03

njzk2 · Answer 2 · 2013-09-23T18:28:53.787

1

What you describe is a circular fifo buffer. You can use Apache Commons-collections implementation.

See Commons Collections and CircularFifoBuffer for documentation

edited Sep 23 '13 at 18:28

answered Sep 23 '13 at 12:02

njzk2

38,969
7
69
107

score 0 · Answer 3 · answered Sep 23 '13 at 11:56

You could do it in the way that you have described but the performance of such a List would be low. Imagine that the limit has been reached and you remove the first element. Under the hood this would involve copying all elements of the underlying array one index up. Then the new element is added to the last index. Especially the copying of all elements is costly

Alternatively you could use a LinkedList, which is more efficient for these kind of operations.

Another way would be to write you own class to implement a Circular Buffer. This is basically an array of size MAX. You have to keep an index of the first element and the number of elements in the array. When you add an element, you check whether the number of elements equals MAX, if so, you overwrite the first element and increase the index of the first element by one. Indexed getters and setters need to take into account the offset of the first element as well, but this is not overly complicated.

The best choice depends on your use case. If you have to do a lot of inserts and deletes at random places in the list, LinkedList is definitely the way to go. If you only want to add items to the end and removing the head, the circular buffer is very efficient.

score 0 · Answer 4 · answered Sep 23 '13 at 11:56

0

IMO, you should be using arrays with a list wrapper. You can then do whatever you want. You can also add methods e.g. get that returns a List.

answered Sep 23 '13 at 11:56

adi

1,711
3
29
50

score 0 · Answer 5 · answered Sep 23 '13 at 11:59

You could use a Deque:

private final int LIMIT = 10;

private Deque<String> queue = new ArrayDeque<String>(LIMIT);

public void addToList(final String element) {
   Deque<String> queue = new ArrayDeque<String>(LIMIT);
   if (!queue.offer(element)) {
      queue.removeFirst();
      queue.offer(element);
   }
}

score 0 · Answer 6 · answered Sep 23 '13 at 12:16

Make your own class that does the job. Keep track of two variables. One for that indicates the zero element and one that holds the position for the next element.

public class MyList<T>
{
    private T array[];
    private int first;
    private int next;
    private int count;

    public MyList(int count)
    {
        array = new T[count];
    }

    public void add(T obj)
    {
        array[next++] = obj;
        next %= array.length;
        if (count == array.length)
        {
            zero = (zero + 1) % array.length;
        } else count++;
    }

    public T get(int index)
    {
        return array[(zero + index) % array.length];
    }
}

List with max elements

6 Answers6