为何java.util.concurrent.PriorityBlockingQueue采用数组而非链表实现？

Great question! Let's break this down clearly to unpack your observations and the reasoning behind these design choices:

• Array's Unbeatable Random Access
  You’re spot-on here—arrays’ biggest strength is their O(1) random access capability. No matter how large the array gets, you can directly jump to any element using its index, which is critical for scenarios like fast lookups, in-place modifications, or any operation that needs to access non-sequential elements. Compare that to standard queues (like those implemented with linked lists), which only allow operations at the head or tail; accessing a middle element requires traversing the entire structure, hitting O(n) time complexity.

• The High Overhead of PriorityBlockingQueue
  Your note about the cost of adding elements to PriorityBlockingQueue is totally valid. This class maintains an ordered collection using a heap structure (backed by an array), and every insertion triggers a heapification process to preserve the priority order. While this isn’t a full shift of all larger/smaller elements, it still carries an O(log n) cost—definitely higher than the O(1) insertion of a basic queue.

• Why Not Use a Linked List for Priority Queues?
  This is the key question, and it boils down to performance tradeoffs:

  • A linked list-based priority queue would require traversing the entire list to find the correct position for each new element, which jumps to O(n) insertion time—worse than the heap’s O(log n).
  • If you used an unordered linked list, retrieving the highest-priority element would also require a full O(n) traversal every time, which is even less efficient.
  • On top of that, array-backed heaps have better space efficiency and cache locality than linked lists, making them faster in practice for most priority queue use cases.

内容的提问来源于stack exchange，提问作者T.Tony