What are the differences between the two common implementations of a queue?

Question

In Java, one of the implementations of queue is "circular array" and the other one is "linked list". What are their differences?

Answer 1

Normally the circular array implementation is slightly better at reusing memory, but runs the risk of having to grow if too many items are added to the queue - and possibly holding too much memory if the normal storage and the max storage capacities are too different in practice.

The linked list is more flexible, but generally involves more garbage collection.

In practice I think I'd be surprised if you found your code bottleneck depended on this choice - use whichever seems most intuitive to you.

Answer 2

In terms of how they're used, there is virtually no difference at all, except when you get to the size limit of the queue (which I'll explain in a sec...)

As for other considerations:

• A linked list approach is advantageous because you can dynamically resize the queue with no extra effort - this is fundamental to linked lists. Of course, this can be replicated by reallocating an array, but it's not the easiest way of doing it.

• Also, in a linked list, there is no unused memory: in a circular array approach, if the size of the queue is less than the maximum capacity of the array, there will be "empty slots". However, this doesn't mean that linked lists are more memory-efficient, because:

• The circular array approach has the advantage that there is no overhead. Each node in a linked list needs to store a reference to the next node - and this adds up if the list gets big. On the other hand, a circular array is just a block of memory which you access by indexing, so there is no overhead.

There are pro's and con's to each approach, but really, it comes down to the specific situation it's used in... and unless you're using queues to no end, it probably won't make much of a difference.

Answer 3

About the same difference as between an ArrayList and a LinkedList.

• For the array, you need to have a good estimate how big the queue can get, because you need to allocate storage for it. But having done that, it is more compact when filled close to capacity. "Free spots" still take up space in the array, which they do not do in the LinkedList.

• For the linked list, it is easier to remove and add elements from the middle (although that should not be needed at all for a queue).

• The array is random access, meaning you can quickly get to the element at position x. Again, this feature is of no use in a queue, though.

Answer 4

A queue implemented as a linked list doesn't have a fixed size, while one implemented as a circular array, aka ring buffer, typically has a fixed size (though it would be possible to make one that resizes, much the way an ArrayList resizes).

The linked list implementation uses more memory per element, but the array implementation requires more contiguous memory. Both of these issues are really only a significant problem as number of elements gets pretty large.

Adding/removing elements to the circular array implementation is very cheap, as it just involves adjusting a counter and setting a reference, while the linked list implementation has to allocate elements when adding, and incurrs GC overhead when removing.

Answer 5

Write your code so that it uses only the interface, except for creation of the queue. Then it is easy to switch implementations.

Pick one implementation for a start. I usually go with the array variants (e.g. ArrayList), because they are smaller and tend to be somewhat faster on todays computers, which I think is due to caching (I just did a little benchmark pushing 10000000 elements through a 10000 element queue, ~8.3s for ArrayBlockingQueue, 10-11s for LinkedBlockingQueue). If I need indexed access I'd also use the array variant. Only if there is a lot of inserting/deleting in the middle of the list or queue I'd chose the linked list variant.

If you have performance issue and profiling shows that the queue is the bottleneck (which is unlikely), benchmark with both implementations of a queue and pick the one which is better.