My problem

Let's say I add messages to some sort of datastructure:

1. "dude"
2. "where"
3. "is"
4. "my"
5. "car"

Asking for messages from index[4,5] should return: "my","car".

Next let's assume that after a while I would like to purge old messages because they aren't useful anymore and I want to save memory. Let's say at time x messages[1-3] became stale. I assume that it would be most efficient to just do the deletion once every x seconds. Next my datastructure should contain:

4. "my"
5. "car"

My solution?

I was thinking of using a concurrentskiplistset or concurrentskiplist map. Also I was thinking of deleting the old messages from inside a newSingleThreadScheduledExecutor. I would like to know how you would implement(efficiently/thread-safe) this or maybe use a library?