Java 集合框架分析：ArrayDeque java1.8

ArrayDeque源码分析
目录
1.ArrayDeque介绍
2.主要方法分析
3.总结

ArrayDeque介绍
实现了Deque接口，作为双向的队列使用
特点：
1.不允许null元素
2.*的，容器满时，自动扩容
3.不是线程安全的。
4.比起作为deque使用时，比linkedlist快（注意：是作为deque,比linkedlist快，而不是作为一个普通的array化的容器）
5.如果是要当作栈这样的结构，且不需要在多线程中使用，性能结构上都比直接使用stack要好。

主要方法分析
先看看主要的成员变量：
head：指向的是当前的头元素节点（当deque不为空时）
tail:指向的是将要插入元素的节点索引位置。
因此，判空逻辑就是 head==tail
判断当前数组是否已经满了的条件就是插入一个元素后，head==tail
初始状态：head=tail=0

   transient Object[] elements; // non-private to simplify nested class access
transient int head;
transient int tail;

1.构造方法

public ArrayDeque() {
        elements = new Object[16];
    }
//如果指定了初始容器的大小，则初始化时，容器大小为第一个大于该值的2^n（严格大于，如初始容量为8，则构造时，容量实际大小为16，如果初始容量为6，则实际大小为8，如果指定的值太小，则初始话成8）

2.addlast
arraydeque是用的环形数组，因为数组大小为2^n，则取模运算被优化成了与运算（在hashmap中也用到了这个技巧！）
因为tail表示的是下一个可用的位置，所以是先插入，在判断是否需要扩容

    public void addLast(E e) {
if (e == null)
throw new NullPointerException();
        elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

3.addfisrt
同addlast,区别是先增加head指针，再插入，再判断。

    public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
            doubleCapacity();
    }

4.removefirst，pollFirst
removefirst直接调用的pollfirst
这里需要注意的是在删除元素时，不能只将元素的head或是tail索引位置改变，还有将相应的元素引用置空！！

    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;
    }

5.removelast，polllast
类似与removefirst,pollfirst

7.size
size=(tail - head) & (elements.length - 1);

总结
特点：
1.底层数组是用的环形数组
2.数组大小为2^n
3.不允许null
4.不是线程安全的。
5.*的

Java 集合框架分析：ArrayDeque java1.8

相关文章