ArrayDeque 源码深度剖析：比 LinkedList

刷 LeetCode 时，很多人习惯用 LinkedList 当队列。其实换成 ArrayDeque，性能能提不少。

它底层是个循环数组，容量永远是 2 的幂。这样取模能用位运算搞定，比普通求余快得多。扩容翻倍后，还会把元素重排得整整齐齐，特别照顾 CPU 缓存。

当栈用时，它比老旧的 Stack 快三到五倍。因为 Stack 带着锁，而它没有同步开销。不过它也有脾气：绝对不允许存 null，也不是线程安全的。

另外它的迭代器不会快速失败。遍历时结构被改了，它不抛异常，但可能读到不一致的数据。而且内存是翻倍涨的，存五千个元素可能占八千多个槽位。

所以只要不用在中间增删、不存 null、不跨线程，它就比链表更省心。