ArrayDeque阅读记录

前言：

1.对Queue接口进行实现

2.底层的数据结构还是数组，同时还是双向的，有前后指针

3.不是线程安全的

4.可以当作队列和栈来使用，选择使用队列时，ArrayDeque推荐首选

5.不可以添加null数据，会抛异常

一些重要变量和常量：

	//元素数组
    transient Object[] elements; 

   //头指针，指向头部的第一个元素的位置
    transient int head;

    //尾指针，将下一个元素添加到尾部的索引，也就是指向尾端第一个可以插入元素的空位
    transient int tail;

   //最小容量，同时必须时2的倍数
    private static final int MIN_INITIAL_CAPACITY = 8;

部分源码分析：

1.初始化对象

    //还是分配16的空间内存 
    public ArrayDeque() {
        elements = new Object[16];
    }

2.添加头节点

    /**
     * 在首部添加节点
     */
    public void addFirst(E e) {
    //如果插入值为空，则抛出异常
        if (e == null)
            throw new NullPointerException();
    //这里定位和之前hashmap中定位table的位置差不多，ArrayDeque本身是一个循环数组，
    //head = (head - 1) & (elements.length - 1)
    //在这里相当于取余操作，同时也保证了下标不为负值
        elements[head = (head - 1) & (elements.length - 1)] = e;
    //添加元素之后，如果头指针和尾指针相同，才会进行扩容，看名字就晓得，扩大两倍
        if (head == tail)
            doubleCapacity();
    }

    //也是添加头节点的方法，这里是返回是否添加成功
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    } 

3.扩容

     /**
     * 扩容操作， 扩大两倍
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        // 头节点右边元素的个数
        int r = n - 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;
    }

4、添加尾节点

   /**
     * 插入节点到尾部
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        //直接添加即可，因为tail指向尾端第一个可以插入元素的空位
        elements[tail] = e;
        //添加之后再做是否需要扩容的判断
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
	
	//也是另外一个添加尾节点的方法，返回成功与否
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

5.删除头结点

    /**
     * 删除头结点，返回删除的元素，如果删除的元素为null,返回null
     */
	public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // 如果队列为空
        if (result == null)
            return null;
        //删除头结点，将头结点这个位置设为null，为了GC
        elements[h] = null;     // Must null out slot
        //头指针前移
        head = (h + 1) & (elements.length - 1);
        return result;
    }

 	/**
     * 这个也是删除头节点，但如果删除的元素为null,抛出异常
     */
    public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

6.删除尾节点

    /**
     * 删除尾结点，返回删除的元素，如果删除的元素为null,返回null
     */
	public E pollLast() {
        //tail是指向尾端第一个可以插入元素的空位，所以他前面就是尾节点的索引，
        //这里进行-1即可获取尾节点的索引地址
        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;
    }

   /**
     * 这个也是删除尾节点，但如果删除的元素为null,抛出异常
     */
    public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

还有些获取某个节点，实现代码都差不多，这里就不一一列出来了，到这ArrayDeque也结束了。