The datastructure you describe sounds totally like a queue. Java has the ConcurrentLinkedQueue for that.
- Add new end of collection : queue.add with O(1)
- Remove : queue.poll O(1)
- Remove from any position : remove O(n)
More on that on
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html
It states there that
This implementation employs an efficient "wait-free" algorithm based on one described in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.