1.声明
当前内容用于本人学习和复习之用，主要为ArrayDequeue的源码分析
2.查看ArrayDeque的继承和实现
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
查看发现ArrayDeque和LinkedList的继承实现都差不多
3.查看ArrayDeque的属性
// 内部维护的数据元素
transient Object[] elements; // non-private to simplify nested class access
// 记录头部的下标
transient int head;
// 记录尾部的下标
transient int tail;
// 最小初始化容量为8，是2的次方
private static final int MIN_INITIAL_CAPACITY = 8;
分析发现：该ArrayDeque内部维护的是一个Object的数组，感觉和ArrayList内部很像
但是该ArrayDeque具有头记录下标和尾记录下标，还有默认最小初始化容量为8
当前的ArrayDeque没有modCount和size(那么它用什么获取实际数据长度？不会出现并发修改？)
4.查看ArrayDeque的构造函数
// 无参构造函数，直接初始化当前数组的容量为16
public ArrayDeque() {
elements = new Object[16];
}
// 有参的构造函数
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 带集合参数的构造函数
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());//计算出容量
addAll(c);// 添加集合数据
}
// 通过计算方式设定当前需要初始化的容量大小
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];//所以这里初始化容量就是2的倍数(最小是8)
}
// 计算容量的大小(结果为2的倍数)，最小为8
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;// 获取最小容量值8
// 如果传递的数比8大，那么需要计算出一个最好的2的次方的数，；例如：传递9返回16，传递17返回32
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
通过分析发现：
- 无参的构造函数中默认创建大小为16的数组对象
- 使用有参的时候，需要通过计算方式获取最好的容量(该容量是2的倍数，最小为8)
- 所以ArrayDeque中只要new出来那么必定初始化当前的容量
5.查看addAll方法
// 该方法为父类提供的方法
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
// 默认循环遍历集合中的所有元素然后进行添加
for (E e : c)
if (add(e))// 这里使用多态方式
modified = true;
return modified;
}
// 实际调用的方法
public boolean add(E e) {
addLast(e);//实际上是向后面添加数据
return true;
}
public void addLast(E e) {
// 添加的数据不能为null，否者报错
if (e == null)
throw new NullPointerException();
elements[tail] = e;// 直接向尾部添加数据
// 然后让该尾下标增加，判断当前的尾下标是否等于最大下标或者是否达到头下标(即判断当前是否需要扩容)
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();//扩容操作，变成原来容量的两倍
}
// 扩容两倍容量
private void doubleCapacity() {
assert head == tail;
int p = head; //获取头下标
int n = elements.length;//获取数组总长
int r = n - p; // 计算左右
int newCapacity = n << 1;// 将原来容量扩容两倍
if (newCapacity < 0) // 判断是否超出最大Integer的最大值，则报错
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;//从新写尾部下标
}
通过分析发现：
添加数据的时候不能放入null值，否则直接空指针异常判断是否需要扩容即尾下标是否达到当前数组的最大值，并且head的前面也是有值的- 如果需要就开始扩容，扩容为原来数组的两倍，
并且使用拷贝方式将有数据的部分放入新数组的前面，前面没有数据的部分放在新数组的后面，最后完成替换操作，并将head设置为0，将尾部下标设置为原来数组的长度 - 默认使用add方法则直接向后面追加值
所以可以发现，这个当前的ArrayDeque使用两个指针方式进行判断哪个部分具有数据，通过头指针方式访问头部，使用尾部指针指向尾部，那么就可实现头部添加和尾部添加(因为知道了当前的头尾部分)
6.查看addFirst方法
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 这里表示head的值计算出来，如果当前的head为0那么结果就是head=31(表示head向后面移动)
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)//如果头部和尾部相碰撞那么认为认为需要扩容了
doubleCapacity();
}
发现这个addFirst方法中使用的如果这个head大于0那么这个头部向后面移动，如果这个数=0那么就从最后一个开始,巧妙地利用逻辑并方式计算出来
7.查看remove方法
//调用删除默认直接删除前面地数据
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)//如果下标元素为null，直接返回null，然后外面出现空指针异常
return null;
// 当前存在元素
elements[h] = null; // 取出后将该元素置空
head = (h + 1) & (elements.length - 1);//然后通过计算方式重新写入头下标(如果在31位置那么直接变成0，如果在1位置那么直接变成2)
return result;
}
通过测试发现：
- remove方法默认是直接移除head下标的元素，如果这个下标中不存在元素，那么直接报错
- 否者认为存在该元素，直接将该元素置空，然后重新计算当前的head下标
查看remove(object)方法
public boolean remove(Object o) {
return removeFirstOccurrence(o);
}
public boolean removeFirstOccurrence(Object o) {
if (o == null)// 判断移除的元素是否为null，是则失败，因为当前的ArrayDeque中不能存放null值
return false;
// 否者可以移除该元素
int mask = elements.length - 1;//获取元素最大下标
int i = head; // 获取头下标的位置
Object x;
// 下面就是使用从head下标向tail下标开始迭代(如果head大于tail,那么从head迭代到最后，然后从0开始到tail)
while ( (x = elements[i]) != null) {
if (o.equals(x)) { // 如果找到它则按照下标方式删除它
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
从分析removeFirstOccurrence(object)方法发现
- 删除默认数据的时候如果head大于tail则从head迭代到最后，然后从0开始迭代到tail位置
- 如果head小于tail那么直接向tail开始迭代
- 找到需要删除的下标，则使用下标方式删除
分析delete(int)方法
// 按照下标方式删除数据
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; // 计算出head到删除的下标i之间的距离(肯定是整数)
final int back = (t - i) & mask; //计算出找到尾节点到当前需要删除的下标i的距离(肯定是整数)
// Invariant: head <= i < tail mod circularity
//如果出现head到i的距离大于尾到头的距离，就认为出现并发操原因作(head <= i < tail)
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
//如果i距离头节点比i距离尾节点近一些
if (front < back) {
if (h <= i) {//判断h是否小于i（即i在h的右边）
System.arraycopy(elements, h, elements, h + 1, front);//直接拷贝方式覆盖即可使用h=h+1，则i位置被h位置的数据覆盖
} else { // Wrap around //整体向后面移动，最后面向第一移动
// 否者认为i在h的左边
System.arraycopy(elements, 0, elements, 1, i);//将第0到i之间的个元素，拷贝到1的后面
elements[0] = elements[mask];//将最后一个元素放到第一个元素中
System.arraycopy(elements, h, elements, h + 1, mask - h);//然后将头下标的元素放到h+1元素的后面
// 整体的思想是，将0到i之间的元素全部向后面移动一位(导致i下标元素被覆盖掉)，空出第一个元素，将头部元素放入第一位
// 然后将h方到h+1的地方形成整体移动的效果，形成最后向第一元素前进1位到达0
}
elements[h] = null;//然后将head下标置空
head = (h + 1) & mask;//head下标改变
return false;
} else {
// 否者认为i距离尾节点比i距离头节点近一些
if (i < t) { // Copy the null tail as well，如果i在尾节点的前面
// 直接拷贝i+1后面的数据拷贝到到i的位置
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;//尾节点减少
} else { // Wrap around// 整体向前移动，将第一个放到最后去
//如果i在尾节点的后面
//将i+1赋值到i上面从而达到覆盖i下标元素的效果(向前拷贝)
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];//将第一个元素放到最后一个元素中
System.arraycopy(elements, 1, elements, 0, t);//然后将i到尾下标的元素放到0的位置，覆盖0
tail = (t - 1) & mask;// 尾下标改变
}
return true;
}
}
通过分析delete(int)方法发现
- 该方法主要用于删除数据，首先获取删除下标到head下标和到tail下标之间的距离
- 然后通过判断是否存在并发操作问题
- 组后比较删除下标到head和tail之间哪个近一些
- 如果距离头部比较近
- 在头部的右边，是则直接拷贝覆盖(向右移动)，最后将head赋值为空即可
- 在头部的左边，认为需要移动整体的数组，全体向右移动，尾部向0开始移动(就像一个环一样)
- 如果距离尾部比较近
- 在尾部的后面，则认为需要移动整体的数组，全体向左移动，头部向数组最大下标移动(向一个环一样)
- 在尾部的前面，直接向前面拷贝
- 如果距离头部比较近
8.分析获取数据的方法
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
由于使用head标记了头元素的下标，可以直接获取
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
直接获取尾元素，所在位置的下标
由于当前的ArrayDeque中将使用head和tail方式所以进行获取操作的时候都是比较简单的！
9.总结
1.ArrayDeque默认无参直接创建16长度的数组，并且每次扩容为原理的两倍
2.ArrayDeque使用Object数组实现与ArrayList一致，但是ArrayDeque中是使用一个head下标和tail进行标记方便删除操作和查找(使用两个指针方式)
3.从理念上来看ArrayDeque的查找和删除效率比当前的LinkedList要高
以上纯属个人见解，如有问题请联本人！
转载：https://blog.csdn.net/weixin_45492007/article/details/106193865
查看评论