ArrayDeque阅读记录

发布时间:2023年12月17日

前言:

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也结束了。

文章来源:https://blog.csdn.net/toward_south/article/details/134960329
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。