Java中的集合之LinkedList,Queue

讨論集合關注的問題：

1. 底層資料結構
2. 增删改查方式
3. 初始容量，擴容方式，擴容時機
4. 線程安全與否
5. 是否允許空，是否允許重複，是否有序

我們都知道Collection接口派生出三大類的子接口List，Set和Queue。今天繼續看List這個系列下的LinkedList，關于ArrayList和Vector前篇已經講過。

Java集合之ArrayList，Vector和Stack

LinkedList和ArrayList都屬于List集合的“範疇”，很大程度上與LinkedList的使用方式類似，差別主要在底層的實作上。顧名思義，LinkedList其底層采用了連結清單的方式來維護集合中的資料。而Queue隊列，是3大類中比較特殊的一類，其子類較少，一般和其他的集合中進行關系的維護。例如LinkedList中就使用了一個雙向隊列。

LinkedList

LinkedList是一個List接口的“範疇”，我這裡說的并不準确，但是一般在開發中采用的“接口+實作類”的方式中，就經常使用List接口來指向其被實作的類，這樣大部分的增删改查的操作方法都可以使用自List接口的調用。

LinkedList繼承自AbstractSequentialList（AbstractList的子類）類，實作了List, Deque, Cloneable, Serializable,說明LinkedList可以進行克隆和序列化操作，其在序列化時，會序列化所有的非空資料。

LinkedList使用一個頭結點first，一個尾節點last，和一個内部類Node來維護集合中的資料，Node是一個具有前後指針的節點結構，來完成連結清單的雙向操作。

LinkedList非線性安全。

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

添加新的元素時，預設添加到連結清單的末尾。同樣可以指定添加的位置，都需要通過first指針一直周遊下去，知道找到合适的位置。添加元素主要是linklast和linkbefore兩個方法：

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }	
	void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
           

在LinkedList中删除元素時，同樣需要通過循環周遊連結清單的指針，找到對應的節點後釋放，相比于ArrayList這個操作僅需修改和釋放(unlink)指針即可，不需要涉及内容的複制。使用Clear将依次周遊指針節點，置為Null.

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
           

LinkedList實作了Deque接口，通過雙向指針的節點，能夠實作雙向隊列的操作；可以擷取頭尾元素，将元素插入頭或者尾部。值得注意的是，LinkedList中的push方法，是将新元素添加到集合的頭部。

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

    /**
     * Retrieves, but does not remove, the last element of this list,
     * or returns {@code null} if this list is empty.
     * @since 1.6
     */
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }
    public void push(E e) {
        addFirst(e);
    }
    public E pop() {
        return removeFirst();
    }
           

Queue

所謂隊列，可以和Stack進行對比，是先進先出或者說後進後出的一種資料結構。在Java集合中，示例UML圖如下，圖檔來源

一般而言，隊列下實作了一個雙向隊列Deque，其被其他集合如上面的LinkedList中繼承而去，主要是實作了連結清單的一些雙向操作的可實施性；另一方面，ArrayDeque主要是使用數組來實作雙向隊列的操作的。還有一類不太常用的優先隊列類。這兩類都是非線性安全的。

ArrayDeque

ArrayDeque通過一個transient修飾的數組和頭尾指針實作，同樣實作了Cloneable, Serializable接口。其初始容量為16。

循環數組：這裡隊列中控制容量大小時2的幂次，每次添加一個元素時，和數組長度做一次與（&）運算，進行判斷是否需要擴容。

public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
    /**
     * Inserts the specified element at the end of this deque.
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
           

PriorityQueue

優先隊列存在一個優先級的概念，不遵循FIFO規則。每次按照優先級最高的資料取出；優先隊列内部維護着一個堆，每次取資料的時候都從堆頂拿資料（堆頂的優先級最高），這就是優先隊列的原理。

總結：

• LinkedList和Queue（ArrayDeque/PriorityQueue）都是非線性安全的
• LinkedList采用連結清單資料結構維護，在删除或插入元素時不需要進行數組的複制，節省記憶體；但是不支援随機通路，需要通過周遊指針來查找。不過，因其底層是一個雙向連結清單，可以友善的對頭尾進行操作。
• ArrayQueue使用數組進行資料維護，PriorityQueue使用堆進行資料維護。