用ArrayDeque比用LinkedList更优于实现Deque？

我就是我 2023-10-04 10:57 6阅读 0赞

问题诱因：[https://leetcode.com/submissions/detail/481019484/][https_leetcode.com_submissions_detail_481019484]中，`Deque<String> l1 = new ArrayDeque<>(Arrays.asList(sentence1.split(" ")));` 用到了ArrayDeque而不是LinkedList。为什么？

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>LinkedList</th> 
   <th>ArrayDeque</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数据结构</td> 
   <td>带头尾结点的双向链表</td> 
   <td>长度为2的幂的环形数组<sup><a rel="nofollow">1</a></sup></td> 
  </tr> 
  <tr> 
   <td>读取效率</td> 
   <td></td> 
   <td>Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.<sup><a rel="nofollow">2</a></sup></td> 
  </tr> 
  <tr> 
   <td>元素可否为null</td> 
   <td>可</td> 
   <td>不可</td> 
  </tr> 
 </tbody> 
</table>

题目中，对Deque的操作主要是去除头尾元素。因为ArrayDeque用的是环形数组，所以即使是读/操作数组头，也不会像ArrayList那样引发其它数组元素的移动，即时间复杂度是O(1)而非O(n)。所以在此题中，即使从效率考虑，可以使用ArrayDeque。在效率方面，LinkedList优于ArrayDeque的唯一操作，应该是随机删。相同观点可见于[https://stackoverflow.com/a/6163204/14993533][https_stackoverflow.com_a_6163204_14993533]

--------------------

1.  源码中pollFirst()方法中的`elements[h] = null; head = (h + 1) & (elements.length - 1);`可为佐证 ↩︎
2.  from jdk1.8官方文档 ↩︎

[https_leetcode.com_submissions_detail_481019484]: https://leetcode.com/submissions/detail/481019484/
[https_stackoverflow.com_a_6163204_14993533]: https://stackoverflow.com/a/6163204/14993533