java集合-ArrayDeque

发表于

类图结构

ArrayDeque是Deque接口的基于可变大小数组实现类。它的类层级结构如图所示：

类文件说明

ArrayDeque和ArrayList一样底层实现是动态数组，没有容量限制，可以动态扩容。ArrayDeque是非线程安全的。ArrayDeque不支持插入null元素。ArrayDeque可以提供Stack一样的操作，但是比Stack更快，因为Stack加了同步锁synchronized。

ArrayDeque的iterator是fail-fast模式的。当返回iterator后，任何不是通过iterator自己的修改函数对ArrayDeque的修改都会抛出异常ConcurrentModificationException。

ArrayDeque底层数据类型：

1
2
3
4
5
6
// 数组
transient Object[] elements; 
// 指向双端队列的头部index
transient int head;
// 指向双端队列的尾部index
transient int tail;

构造函数

ArrayDeque有三个构造函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 默认动态数组初始容量为16
public ArrayDeque() {
  elements = new Object[16];
}

// 显式传入元素个数，但是allocateElements函数会对元素个数进行向上取2的幂次方
// 比如传入28，实际初始容量会是32
public ArrayDeque(int numElements) {
  allocateElements(numElements);
}

// 根据指定集合初始化
// 首先根据集合的容量和allocateElements函数确定ArrayDeque的初始容量
// addAll会从尾端tail添加集合里的元素
public ArrayDeque(Collection<? extends E> c) {
  allocateElements(c.size());
  addAll(c);
}

addFirst

addFirst从双端队列的头部head添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void addFirst(E e) {
  // 不支持null元素
  if (e == null)
    throw new NullPointerException();
  // 初始化完成：head == tail == 0
  // 假设初始容量为16: 则:
  // head = (head - 1) & (elements.length - 1)
  // head = -1 & 15 
  // head = 15
  // 将元素插入数组最末尾位置，head也相应指向数组最末尾位置
  elements[head = (head - 1) & (elements.length - 1)] = e;
  // 此时 head == 15, tail == 0，不需要扩容
  if (head == tail)
    doubleCapacity();
}

在添加元素途中仅当数组满了的时候（head == tail）才进行扩容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void doubleCapacity() {
  assert head == tail;
  // 获取此时头部索引位置
  int p = head;
  int n = elements.length;
  // 获取此时头部索引位置到数组末端元素个数
  int r = n - p; // number of elements to the right of p
  // 扩容两倍
  int newCapacity = n << 1;
  if (newCapacity < 0)
    throw new IllegalStateException("Sorry, deque too big");
  Object[] a = new Object[newCapacity];
  // 首先拷贝原头部索引位置到数组末端的元素到新数组
  System.arraycopy(elements, p, a, 0, r);
  // 再拷贝原数组首部到头部索引位置元素到新数组
  System.arraycopy(elements, 0, a, r, p);
  elements = a;
  head = 0;
  tail = n;
}

扩容前后示意图如下：

扩容前：

扩容后：

addLast

addFirst从双端队列的尾部tail添加元素

1
2
3
4
5
6
7
8
9
10
11
12
public void addLast(E e) {
  // 不支持null元素
  if (e == null)
    throw new NullPointerException();
  // 直接赋值到tail索引所在的位置
  // 可知tail是指向尾部元素的下一个位置
  elements[tail] = e;
  // 然后将尾部索引tail加1
  // 判断tail == head时扩容
  if ( (tail = (tail + 1) & (elements.length - 1)) == head)
    doubleCapacity();
}

get

getFirst从双端队列头部获取元素，getLast从双端队列尾部获取元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E getFirst() {
  @SuppressWarnings("unchecked")
  // 从头部获取元素，直接返回head索引所在位置的元素
  E result = (E) elements[head];
  if (result == null)
    throw new NoSuchElementException();
  return result;
}

public E getLast() {
  @SuppressWarnings("unchecked")
  // 从尾部获取元素
  // 首先将tail - 1
  // 然后返回tail - 1索引所在位置的元素
  E result = (E) elements[(tail - 1) & (elements.length - 1)];
  if (result == null)
    throw new NoSuchElementException();
  return result;
}

remove

remove默认从头节点删除元素，然后将head指向下一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public E remove() {
  return removeFirst();
}

public E removeFirst() {
  E x = pollFirst();
  if (x == null)
    throw new NoSuchElementException();
  return x;
}

public E pollFirst() {
  int h = head;
  @SuppressWarnings("unchecked")
  E result = (E) elements[h];
  // Element is null if deque empty
  if (result == null)
    return null;
  //将删除的原head索引位置的元素置为null
  elements[h] = null;     // Must null out slot
  // 将head索引后移一个位置
  head = (h + 1) & (elements.length - 1);
  return result;
}

remove(Object o)指定的元素默认删除从head索引开始查找第一次出现的元素，如下可知删除指定元素，需要重新拷贝元素，是很耗性能的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public boolean remove(Object o) {
  return removeFirstOccurrence(o);
}

public boolean removeFirstOccurrence(Object o) {
  // 不支持null元素
  if (o == null)
    return false;
  int mask = elements.length - 1;
  int i = head;
  Object x;
  // 从head索引位置开始查找
  while ( (x = elements[i]) != null) {
    if (o.equals(x)) {
      //第一次出现即删除
      delete(i);
      return true;
    }
    i = (i + 1) & mask;
  }
  return false;
}

private boolean delete(int i) {
  checkInvariants();
  final Object[] elements = this.elements;
  final int mask = elements.length - 1;
  final int h = head;
  final int t = tail;
  // front表示待删除元素到head索引位置的距离
  final int front = (i - h) & mask;
  // back表示待删除元素到tail索引位置的距离
  final int back  = (t - i) & mask;

  // Invariant: head <= i < tail mod circularity
  if (front >= ((t - h) & mask))
    throw new ConcurrentModificationException();

  // Optimize for least element motion
  // 比较front、back的大小，减少不必要copy的元素
  if (front < back) {
    if (h <= i) {
      System.arraycopy(elements, h, elements, h + 1, front);
    } else { // Wrap around
      System.arraycopy(elements, 0, elements, 1, i);
      elements[0] = elements[mask];
      System.arraycopy(elements, h, elements, h + 1, mask - h);
    }
    elements[h] = null;
    head = (h + 1) & mask;
    return false;
  } else {
    if (i < t) { // Copy the null tail as well
      System.arraycopy(elements, i + 1, elements, i, back);
      tail = t - 1;
    } else { // Wrap around
      System.arraycopy(elements, i + 1, elements, i, mask - i);
      elements[mask] = elements[0];
      System.arraycopy(elements, 1, elements, 0, t);
      tail = (t - 1) & mask;
    }
    return true;
  }
}
-------------本文结束感谢您的阅读-------------
Good for you!