【JAVA基礎——LinkedList】

學習記錄之路。。。

LinkedList雙向連結清單實作的接口清單和deque容器。實作所有可選的清單操作，并允許所有元素（包括null）。

先來看一下LinkedList 類 的建立：

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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() {
    }
           

實作的接口有四個， 分别是清單接口，隊列接口，克隆标記類，序列化标記類。 

這裡順便提一下 “transient”：表示臨時性， 也就是說，被修飾的變量，不會被序列化。（需要了解的可以自行查找資料）

接下來是連結清單的源碼的核心代碼：

核心思想是在内部建立了一個内部類Node，通過内部類來存放連結清單中的元素。下面是源碼節選：

/**
     * Node對象， 連結清單的每個節點都存儲了， 上個一個節點标記， 目前節點元素， 下一個節點标記 ， 三個值。
     *
     * 是以采用，定義一個Node對象來存這三個值。 注意： 三個參數。
     * @param <E>
     */
    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;
        }
    }
           

幾乎每個方法都會建立這個對象，來對連結清單元素進行添加等的操作。例如下面的這個addFirst()方法：

/**
     * Inserts the specified element at the beginning of this list.
     * 在清單的頭部插入指定的元素
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }
           

/**
     * Links e as first element.
     *
     *添加第一個元素時， 是第一個元素，也是最後一個元素。
     *
     * 建立了一個Node對象，裡面有三個Node對象？ 上一個節點，目前節點，下一個節點，
     *
     * 添加的元素，都指派給Node對象的item（目前節點）上。
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
           

源碼就到這裡結束，其他都跟這個思路差不多，這裡就不貼了。

LinkedList 的方法很多，由于他是兩個接口的實作類，是以，會根據清單，還是隊列的實作會用不同的方法。

下面是連結清單的部分方法（來自jdk7）：