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.

Answer 2

There is a related question here with a solution: LinkedList Vs ConcurrentLinkedQueue

The answer suggests using a ConcurrentLinkedQueue. From your question it turns out that you want a queue/linked list like behaviour so I think this will help you.

Answer 3

You can use a ConcurrentLinkedQueue for this since both offer(E) and poll() process your most likely operations in constant time. (I suggested a ConcurrentLinkedDeque first, but I misread that you wanted to add and remove elements at the same side of the queue. Since this is not a requirement prefer the one-sided queue.)

The only downside of this choice is that you would need to iterate over n entries of the Deque in order to remove the n-th element. Also, this operation would be blocking or would offer fail-potential since the javadoc states:

The returned iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

Other than that, this queue will perform very well on the two other tasks (adding or removing from both ends) since the queue is non-blocking for concurrent operations what is something you want when efficiency matters.