Looking for datastructure that maintains a size & purges older elements in the process

Question

Usecase maintain a list of the last n visited URLs (where n is a fix number). As new URLs are added to the list, older urls are removed automatically (in order to keep it at n elements)

Requirement The data structure needs to be sorted by time (should be no problem if it accepts a Comparator).

Answer 1

You need a circular buffer.

Just keep an array b[] of size N and index k, that points to the oldest URL. Every time you need to add new URL, assign it to b[k] and increment k, wrapping it if needed: k = (k + 1) % N.

All your URLs will be naturally sorted, the oldest is at k, the second oldest at k+1, and so on, the newest is at k-1. (The sequence wraps at the end of the array).

Answer 2

In java there are several implementation of Queue. It should be trivial to inherit or warp an existing implementation and implement the add() method like this:

boolean add(E e) {
  if(q.size()==MAX_SIZE) {
    remove();
  }
  q.add(e)
}

Answer 3

Use a circular buffer of size n