Java ArrayDeque源码学习

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable 1.6

双端队列的动态数组实现
This class is likely to be faster than when used as a stack, and faster than LinkedList when used as a queue.

1. 数组大小分配算法
   2 ^ n <= numElements < 2 ^ (n+1) 分配 2 ^ (n+1)大小。
   最少分配8，最多分配2 ^ 30个元素。

       /**
        * The minimum capacity that we'll use for a newly created deque.
        * Must be a power of 2.
        */
       private static final int MIN_INITIAL_CAPACITY = 8;
   
       // ******  Array allocation and resizing utilities ******
   
       private static int calculateSize(int numElements) {
           int initialCapacity = MIN_INITIAL_CAPACITY;
           // Find the best power of two to hold elements.
           // Tests "<=" because arrays aren't kept full.
           if (numElements >= initialCapacity) {
               initialCapacity = numElements;
               initialCapacity |= (initialCapacity >>>  1); //前2位为1
               initialCapacity |= (initialCapacity >>>  2); //前4位为1
               initialCapacity |= (initialCapacity >>>  4); //前8位为1
               initialCapacity |= (initialCapacity >>>  8); //前16位为1
               initialCapacity |= (initialCapacity >>> 16); //前32位为1
               initialCapacity++; //进1位
               if (initialCapacity < 0)   // Too many elements, must back off
                   initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
           }
           return initialCapacity;
       }
   

2. 容量扩充，加倍操作

   /**
    * Doubles the capacity of this deque.  Call only when full, i.e.,
    * when head and tail have wrapped around to become equal.
    */
   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;
   }
   ```   ​
   

3. 移动 机智的&操作
   index & (elements.length - 1) 从0开始到最后一位，然后回到第0位。
   (index+elements.length) % elements.length 取模也可以，性能不如位运算；

   public void addFirst(E e) {
        if (e == null)
        throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
          doubleCapacity();
   }
   public void addLast(E e) {
       if (e == null)
           throw new NullPointerException();
       elements[tail] = e;
       if ( (tail = (tail + 1) & (elements.length - 1)) == head)
           doubleCapacity();//空间满了，加倍
   }
   

   public E pollLast() {
       int t = (tail - 1) & (elements.length - 1);
       @SuppressWarnings("unchecked")
       E result = (E) elements[t];
       if (result == null)
           return null;
       elements[t] = null;
       tail = t;
       return result;
   }
   

   size

   public int size() {
       return (tail - head) & (elements.length - 1);//-3与7，刚好是8减3
   }
   

4. 删除操作，删除中间某个节点需要数组的移动。 有意思
   如果删除节点靠近头结点，则移动前半部分，返回false；
   如果删除节点靠近尾结点，则移动后半部分，返回true；-> 实现最少的数组移动

   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;
       final int front = (i - h) & mask;
       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
       if (front < back) {//删除节点靠近头结点
           if (h <= i) { //删除节点在头结点后边，将front部分后移即可
               System.arraycopy(elements, h, elements, h + 1, front);
           } else { // 删除节点在头结点前边，分段处理
               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;
       }
   }
   

   ArrayDeque并不提供index访问，所以此函数只用于removeFirstOccurrence或者Iterator.remove

@梦工厂2018.3.10