0%

Java 列表和队列（三）：剖析 ArrayDeque

发表于 更新于 分类于
本文字数： 733 阅读时长 ≈ 1 分钟

1. ArrayDeque 的实现原理是

  • ArrayDeque 内部是一个动态扩展的逻辑上的循环数组

    • 通过 head 和 tail 变量维护数组的开始和结尾，数组长度为 2 的幂次方
    • 使用高效的位操作进行各种判断，以及对 head 和 tail 进行维护

  • ArrayDeque 的高效来源于 head 和 tail 这两个变量

    • 它们使得物理上简单的从头到尾的数组变成了一个逻辑上循环的数组，避免了在头尾操作时的移动
    • 所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度、第一个和最后一个元素都与 head 和 tail 这两个变量有关

  • ArrayDeque 内部主要有如下实例变量

    1
    2
    3
    private transient E[] elements;
    private transient int head;
    private transient int tail;

2. ArrayDeque 有什么特点

  • ArrayDeque 实现了双端队列 Deque，内部使用循环数组实现
  • 在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组复制开销可以被平摊。具体来说，添加 N 个元素的效率为 O(N)；根据元素内容查找和删除的效率比较低，为 O(N)
  • 与 ArrayList 和 LinkedList 不同，ArrayDeque 没有索引位置的概念，所以不能根据索引位置进行操作
  • 无论 ArrayList、LinkedList 还是 ArrayDeque ，按内容查找元素的效率都很低，都需要逐个进行比较

3. ArrayDeque 和 LinkedList 都实现了 Deque 接口，应该用哪一个

  • 如果只需要 Deque 接口从两端进行操作，一般而言，ArrayDeque 效率更高一些，应该被优先使用
  • 如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除操作，则应该选 LinkedList
-------------------- 本文结束感谢您的阅读 --------------------