Java concurrent: choose synchronized collection

Question

I want concurrently do the next things:

1. Add new item at the end of collection (often)
2. Remove item (or few items) from the begining of collection (often)
3. Remove item (or few items) from the middle of collection (rarely, happens by iterating all items)

Question: which concurrent collection will give me the best performance.

EDIT: (how happens removing from the middle)

I'll iterate the whole collection, find begIndex and remove n next elements beggining from begIndex.

Answer 1

The datastructure you describe sounds totally like a queue. Java has the ConcurrentLinkedQueue for that.

1. Add new end of collection : queue.add with O(1)
2. Remove : queue.poll O(1)
3. 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.