博客

前言

本文整理了List、Queue的相关知识，介绍相关的实现类，附有相关的源码以及自己的一点理解。如有不对，欢迎指正。

List

LinkedList、ArrayList、Vector的区别

ArrayList

采用数组的形式，使用一段连续的线性存储空间，更适合随机查找和遍历，不适合插入和删除。

代码实现及构造方法

	
	/**
	 * The array buffer into which the elements of the ArrayList are stored.
	 * The capacity of the ArrayList is the length of this array buffer. Any
	 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
	 * will be expanded to DEFAULT_CAPACITY when the first element is added.
	 */
	transient Object[] elementData; // non-private to simplify nested class access

	/**
	 * The size of the ArrayList (the number of elements it contains).
	 */
	private int size;

	/**
	 * Constructs an empty list with the specified initial capacity.
	 *
	 * @param  initialCapacity  the initial capacity of the list
	 * @throws IllegalArgumentException if the specified initial capacity
	 *         is negative
	 */
	public ArrayList(int initialCapacity) {
	    if (initialCapacity > 0) {
	        this.elementData = new Object[initialCapacity];
	    } else if (initialCapacity == 0) {
	        this.elementData = EMPTY_ELEMENTDATA;
	    } else {
	        throw new IllegalArgumentException("Illegal Capacity: "+
	                                           initialCapacity);
	    }
	}
	
	/**
	 * Constructs an empty list with an initial capacity of ten.
	 */
	public ArrayList() {
	    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}
	
	/**
	 * Constructs a list containing the elements of the specified
	 * collection, in the order they are returned by the collection's
	 * iterator.
	 *
	 * @param c the collection whose elements are to be placed into this list
	 * @throws NullPointerException if the specified collection is null
	 */
	public ArrayList(Collection<? extends E> c) {
	    elementData = c.toArray();
	    if ((size = elementData.length) != 0) {
	        // c.toArray might (incorrectly) not return Object[] (see 6260652)
	        if (elementData.getClass() != Object[].class)
	            elementData = Arrays.copyOf(elementData, size, Object[].class);
	    } else {
	        // replace with empty array.
	        this.elementData = EMPTY_ELEMENTDATA;
	    }
	}

常见方法

• add(E e)
• add(int index, E element)
• addAll(Collection<? extends E> c)
• set(int index, E element)
• get(int index)
• remove(int index)
• indexOf(Object o)
• lastIndexOf(Object o) 获取元素的最后一次出现的index:

补充

• 下标越界检查：对于有关index的方法，会先调用
  
rangeCheck(index)

  进行检查是否越界。
• 容器检查机制：在进行增加操作的时候会先调用
  
ensureCapacityInternal(size + 1)

  ，当数组下标不够使用的时候，扩展到原来的1.5倍
  
newCapacity = oldCapacity + (oldCapacity >> 1);

• Fail-Fast机制: ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

和Vector的对比

1. 线程安全

   ArrayList线程不安全，没有实现同步(synchronized)，Vector线程安全，实现同步，但因为锁粒度大，所以弃用。

2. 扩容机制

   Vector进行翻倍扩容，ArrayList只增加一半。

LinkedList

同时实现了List接口和Deque接口，既可以作为一个顺序容器，也可以看作是一个栈或者队列。

关于栈或队列，现在的首选是_ArrayDeque_，它有着比_LinkedList_(当作栈或队列使用时)有着更好的性能。

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

代码实现及构造方法

	
	transient int size = 0;
	
	/**
	 * Pointer to first node.
	 * Invariant: (first == null && last == null) ||
	 *            (first.prev == null && first.item != null)
	 */
	transient Node<E> first;
	
	/**
	 * Pointer to last node.
	 * Invariant: (first == null && last == null) ||
	 *            (last.next == null && last.item != null)
	 */
	transient Node<E> last;
	
	/**
	 * Constructs an empty list.
	 */
	public LinkedList() {
	}
	
	/**
	 * Constructs a list containing the elements of the specified
	 * collection, in the order they are returned by the collection's
	 * iterator.
	 *
	 * @param  c the collection whose elements are to be placed into this list
	 * @throws NullPointerException if the specified collection is null
	 */
	public LinkedList(Collection<? extends E> c) {
	    this();
	    addAll(c);
	}
	
	
	private static class Node<E> {
	    E item;
	    Node<E> next;
	    Node<E> prev;
	
	    Node(Node<E> prev, E element, Node<E> next) {
	        this.item = element;
	        this.next = next;
	        this.prev = prev;
	    }
	}
  

常见方法

• getFirst()
• getLast()
• removeFirest()，removeLast()
• remove(Object o)
• remove(index)）
• add(E e)
• add(int index, E element)
• clear()

补充：

• 下标越界检查：在调用index的时候，会进行下标越界检查
  
checkPositionIndex(index)

• 查找开端判断：链表是双向的，具有next、prev指针，查找方向取决于条件index < (size >> 1)，判断靠近哪一端。
• unlink方法：在删除的时候会调用unlink方法，在unlink方法中会将待删除的元素和next元素设置为空，帮助进行JVM垃圾回收。

ArrayList 和 LinkedList的区别

ArrayList和LinkedList都实现了List接口，有以下的不同点：

1. 底层实现

ArrayList基于索引（下标）形式存储数据，底层用数组实现，便于基于index的查找，时间复杂度为

O(1)

，由于在增加、删除操作可能会出现空间碎片且需要重新计算大小以及更新索引，所以不利于增删操作。LinkedList基于元素相互链接形式存储数据，底层用链表实现，便于插入和删除，不利于涉及位置的查找，时间复杂度为

O(N)

。

2. 空间占用

LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

Queue

PriorityQueue

PriorityQueue

，即优先队列。优先队列实际上是维护一个堆结构，在Java的优先队列中默认实现小顶堆，即每次取出来的元素都是最小的（放在队首），排序规则可以通过元素本身的自然顺序，也可以通过构造时传入的比较器_Comparator**。**_

数组下标的映射


优先队列底层是数组实现，而维护堆特性主要依靠数组下标的映射规则。

• 左节点：
  
leftNo = parentNo * 2 + 1

  –>
  
child = (k << 1) + 1;

• 右节点：
  
rightNo = parentNo * 2 + 2

  –>
  
right = child + 1;

• 父节点：
  
parentNo = (nodeNo - 1) / 2

  –>
  
parent = (k - 1) >>> 1;


常见方法

小顶堆的维护

主要依赖于

siftUp()

和

siftDown(

)的实现，两者都是维护堆的实现，前者用于插入元素，后者用于删除元素。

• 加入元素，元素x 放在队列末尾。调用
  
siftUp(int k, E x)

  ，k 标注的是队尾下标，x 是待插入元素。默认的比较逻辑是与前面父节点进行比较，如果比父节点小，进行交换。也可以用比较器自定义比较逻辑。
• 删除元素，分成两种情况，分别删除节点是队尾或者是其他位置。具体实现是找到待删除节点的坐标，判断情况，前者直接令删除节点为空，后者调用
  
siftDown(int index, E x)

  ，此处index是删除节点的位置，x是队尾元素。


siftUp



siftDown


相关源码

	// offer(E e)
	public boolean offer(E e) {
	    if (e == null)//不允许放入null元素
	        throw new NullPointerException();
	    modCount++;
	    int i = size;
	    if (i >= queue.length)
	        grow(i + 1);//自动扩容
	    size = i + 1;
	    if (i == 0)//队列原来为空，这是插入的第一个元素
	        queue[0] = e;
	    else
	        siftUp(i, e);//调整
	    return true;
	}
	
	// siftUp()
	private void siftUp(int k, E x) {
	    while (k > 0) {
	        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
	        Object e = queue[parent];
	        if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
	            break;
	        queue[k] = e;
	        k = parent;
	    }
	    queue[k] = x;
	}
	
	// siftDown()
	private void siftDown(int k, E x) {
	    int half = size >>> 1;
	    while (k < half) {
	    	// 首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
	        int child = (k << 1) + 1; //leftNo = parentNo*2+1
	        Object c = queue[child];
	        int right = child + 1;
	        if (right < size &&
	            comparator.compare((E) c, (E) queue[right]) > 0)
	            c = queue[child = right];
	        if (comparator.compare(x, (E) c) <= 0)
	            break;
	        queue[k] = c; //然后用c取代原来的值
	        k = child;
	    }
	    queue[k] = x;
	}

	// remove(Object o)
	public boolean remove(Object o) {
		//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
	    int i = indexOf(o);
	    if (i == -1)
	        return false;
	    int s = --size;
	    if (s == i) //情况1
	        queue[i] = null;
	    else {
	        E moved = (E) queue[s];
	        queue[s] = null;
	        siftDown(i, moved);//情况2
	        ......
	    }
	    return true;
	}

Deque

Deque是”double ended queue”, 表示双向队列。继承Queue接口，还支持insert, remove和examine操作。是双向队列，所以可以对队列两端进行操作。常见方法可能返回false，也可能抛出异常。

常见方法

ArrayDeque

对于栈和队列的实现，官方更加推荐ArrayDeque。ArrayQueue底层基于会扩容的数组实现，为了提高性能，采用循环数组的实现，即数据在逻辑上连续，但物理上被分成了两截。对于数组的空间长度，为了方便进行与运算，所以使用2的整数倍，默认是16。

大多数ArrayDeque操作运行在平摊常量时间内。异常包括remove、removeFirstOccurrence、removeLastOccurrence、contains、iterator.remove()和bulk操作，所有这些操作都在线性时间内运行。

基本元素

    //存放元素的数组，长度永远为2的幂，如果数组满了就会立刻扩容
    transient Object[] elements; // non-private to simplify nested class access

    //头节点的索引
    transient int head;

    //元素被添加的位置的索引
    transient int tail;

    //最小容量，一定2的幂
    private static final int MIN_INITIAL_CAPACITY = 8;

常见方法

• addFirst(E e)
• addLast(E e)
• pollFirst()
• pollLast()
• peekFirst()
• peekLast()

扩容机制

1. 扩容时间：当头、尾两指针相遇的时候，调用
   
doubleCapacity()

   。在增加的时候，都是先进行赋值，再检查容量。
2. 扩容机制：逻辑是申请一个更大的数组(原数组的两倍)，然后将原数组复制过去。在数组长度已知的情况下，可以直接new一个定长的数组，这样就不需要
   
Array.copyOfRange

   函数，可以统一使用
   
System.arrayCopy。

   在复制的时候，先复制右侧，再复制左侧。

	//doubleCapacity()
	private void doubleCapacity() {
	    assert head == tail;
	    int p = head;
	    int n = elements.length;
	    int r = n - p; // head右边元素的个数
	    int newCapacity = n << 1;//原空间的2倍
	    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 = (E[])a;
	    head = 0;
	    tail = n;
	}

补充

1. 在循环数组中，数据可能被分两块。所以在进行增加操作时，需要判断加入位置下标是在左侧还是右侧。

   • 对于队首，指针下标不断向后退，当退到索引0时，重新回到空间数组的右端。

     
elements[head = (head - 1) & (elements.length - 1)] = e;


   • 对于队尾，指针下标不断向前扩展，到达空间数组下标后，重新回到0指针。

2. 计算队列长度，如果物理上不连续，需要特别计算真正的数据。ArrayDeque使用了位与运算实现：
   
return (tail - head) & (elements.length - 1);


3. 删除中间某个数据时，在左侧或右侧删除，然后挪动头或者尾。删除中间元素时，先判断中间元素里head近还是离tail近，然后移动较近的那一端。此时移动逻辑上较近的一端，但仍需要做两次数组元素的批量移动。

4. 当
   
head = -1

   的时候，在计算机中,-1的二进制是11111111，所以最后的与运算结果为
   
elements.length - 1

   。

相关代码

	//addFirst(E e)
	public void addFirst(E e) {
	    if (e == null)//不允许放入null
	        throw new NullPointerException();
	    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
	    if (head == tail)//1.空间是否够用
	        doubleCapacity();//扩容
	}
	
	//addLast(E e)
	public void addLast(E e) {
	    if (e == null)//不允许放入null
	        throw new NullPointerException();
	    elements[tail] = e;//赋值
	    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
	        doubleCapacity();//扩容
	}

参考文章

pdai Java 全栈知识体系



深入理解ArrayDeque的设计与实现