[sudarshnachakra]

I guess linked lists as they are are very useful for implementing queues (particularly those that feed thread pools) where-in the costs of growable array is not needed and the cache locality does not matter (continuing with a thread pool example - It's almost a guarantee that having next element in the cache of the CPU which is not going to execute the next Runnable is a waste).

In Java particularly the both array as well as the linked implementation of blocking queues should perform equally well. FWIW most queue implementations are linked lists.

[NavinF]

The best implementations typically have a queue per thread and work stealing. The first threads to finish their assigned work will grab items from other queues, but until then you get perfect cache locality.

Java's queues and global threadpool queues in general are pretty old hat.