Java: ArrayBlockingQueue vs. LinkedBlockingQueue

Question

I think that, in most cases, the ArrayBlockingQueue will perform better than the LinkedBlockingQueue. However, that is the case when there is always enough room in the array... If it gets full, it's not very predictable whether it will perform so well, since it will block the thread that's trying to push data into the queue...

So, my question is: Is there any middle-ground implementation of BlockingQueue? Say, an ArrayListBlockingQueue or a BucketListBlockingQueue? Something like a list of arrays, so that the queue can increase in capacity dynamically, while still having a reasonable benefit from using array to ultimately store data?

Answer 1

1 . LinkedBlockingQueue ( LinkedList Implementation but not exactly JDK Implementation of LinkedList. It uses static inner class Node to maintain Links between elements )

Constructor for LinkedBlockingQueue
public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Node class used to maintain Links

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

2 . ArrayBlockingQueue ( Array Implementation )

Constructor for ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

Biggest difference between ArrayBlockingQueue and LinkedBlockingQueue is clear from constructor, one has an underlying data structure of Array and the other of LinkedList.

ArrayBlockingQueue uses single-lock double condition algorithm and LinkedBlockingQueue is a variant of the "two lock queue" algorithm and it has 2 locks 2 conditions ( takeLock , putLock)

Till now I gave comparison between these 2 implementations Coming back to original question , Similar question was asked in concurrency mailing list in this doug Lea talks about DynamicArrayBlockingQueue which is implementation provided by Dawid Kurzyniec.