摘要：說明是對鏈表的擴(kuò)展，其底層使用鏈表實(shí)現(xiàn)，不是線程安全的集合類。其繼承，實(shí)現(xiàn)了各個接口，其中繼承了抽象類，是對支持隨機(jī)讀取的的部分功能的抽象，是對不支持隨機(jī)讀取的的一部分功能的抽象。并且實(shí)現(xiàn)了接口，代表其支持雙端隊(duì)列的所有功能。

LinkedList是對鏈表的擴(kuò)展，其底層使用鏈表實(shí)現(xiàn)，不是線程安全的集合類。其繼承AbstractSequentialList，實(shí)現(xiàn)了List, Deque, Cloneable,Serializable各個接口，其中AbstractSequentialList繼承了AbstractList抽象類，AbstractList是對支持隨機(jī)讀取的List的部分功能的抽象，AbstractSequentialList是對不支持隨機(jī)讀取的List的一部分功能的抽象。并且LinkedList實(shí)現(xiàn)了Deque接口，代表其支持雙端隊(duì)列的所有功能。

LinkedList首先是鏈表的擴(kuò)展，并且實(shí)現(xiàn)了雙端隊(duì)列的接口，所以其特點(diǎn)如下：

隨機(jī)存儲，優(yōu)點(diǎn)是不需要提前申請空間

具有雙端隊(duì)列的所有功能，可以簡單地實(shí)現(xiàn)先進(jìn)先出和后進(jìn)先出

新增和刪除時間復(fù)雜度比較少

//元素的個數(shù)
transient int size = 0;

//首節(jié)點(diǎn)
transient Node first;

//尾節(jié)點(diǎn)
transient Node last;

在此之前，先介紹一下雙端鏈表的數(shù)據(jù)結(jié)構(gòu)

private static class Node {
        //節(jié)點(diǎn)的值
        E item;
        //下一個節(jié)點(diǎn)，如果為尾節(jié)點(diǎn)，則此值為null
        Node next;
        //前一個節(jié)點(diǎn)，如果為首節(jié)點(diǎn)，則此值為null
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

//向鏈表頭添加元素
private void linkFirst(E e) {
        final Node f = first;
        //設(shè)置新節(jié)點(diǎn)，令首節(jié)點(diǎn)等于新節(jié)點(diǎn)，并將新節(jié)點(diǎn)的next指向原來的首節(jié)點(diǎn)
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        //如果原來首節(jié)點(diǎn)為空，代表為空鏈表，則令尾節(jié)點(diǎn)也為新節(jié)點(diǎn)
          ，否則，令原來首節(jié)點(diǎn)的前一個節(jié)點(diǎn)為新節(jié)點(diǎn)
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        //元素個數(shù)與修改次數(shù)進(jìn)行增加
        size++;
        modCount++;
    }
    
//向鏈表尾添加元素
void linkLast(E e) {
        final Node l = last;
        //設(shè)置新節(jié)點(diǎn)，令尾節(jié)點(diǎn)指向新節(jié)點(diǎn)，并且將新節(jié)點(diǎn)的prev指向原來的尾節(jié)點(diǎn)
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        //如果原來尾節(jié)點(diǎn)為空，代表為空鏈表，則令首節(jié)點(diǎn)也為新節(jié)點(diǎn)
          ，否則，令原來尾節(jié)點(diǎn)的下一個節(jié)點(diǎn)為新節(jié)點(diǎn)
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

//在給定節(jié)點(diǎn)之前插入對應(yīng)節(jié)點(diǎn)
void linkBefore(E e, Node succ) {
        //獲取給定節(jié)點(diǎn)的前一個節(jié)點(diǎn)，設(shè)為pred
        final Node pred = succ.prev;
        //設(shè)置新節(jié)點(diǎn)，令其prev為給定節(jié)點(diǎn)的前一個節(jié)點(diǎn)，next為給定節(jié)點(diǎn)
        final Node newNode = new Node<>(pred, e, succ);
        //同時設(shè)置給定節(jié)點(diǎn)的前一個節(jié)點(diǎn)為新節(jié)點(diǎn)
        succ.prev = newNode;
        //判斷pred是否為空，如果是，那么新節(jié)點(diǎn)就是首節(jié)點(diǎn)
          ，否則，直接令pred的下一個節(jié)點(diǎn)為新節(jié)點(diǎn)
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

//刪除首節(jié)點(diǎn)
private E unlinkFirst(Node f) {
        final E element = f.item;
        final Node next = f.next;
        //將首節(jié)點(diǎn)中相關(guān)引用置空，防止內(nèi)存泄漏
        f.item = null;
        f.next = null;
        //令首節(jié)點(diǎn)為首節(jié)點(diǎn)的下一個節(jié)點(diǎn)
        first = next;
        //如果首節(jié)點(diǎn)為空，那么直接將尾節(jié)點(diǎn)也置空，
          否則，將當(dāng)前首節(jié)點(diǎn)的prev置為null
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
//刪除尾節(jié)點(diǎn)
private E unlinkLast(Node l) {
        final E element = l.item;
        final Node prev = l.prev;
        //將尾節(jié)點(diǎn)中相關(guān)引用置空，防止內(nèi)存泄漏
        l.item = null;
        l.prev = null; 
        //令尾節(jié)點(diǎn)為尾節(jié)點(diǎn)的前一個節(jié)點(diǎn)
        last = prev;
        //如果尾節(jié)點(diǎn)為空，那么直接將首節(jié)點(diǎn)也置空，
          否則，將當(dāng)前尾節(jié)點(diǎn)的next置為null
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    
//刪除指定元素
E unlink(Node x) {
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;
        
        //如果指定節(jié)點(diǎn)的前一個節(jié)點(diǎn)為空，代表制定節(jié)點(diǎn)為首節(jié)點(diǎn)
          ，令首節(jié)點(diǎn)為指定節(jié)點(diǎn)的下一個節(jié)點(diǎn)，否則，指定節(jié)點(diǎn)
          的prev的next節(jié)點(diǎn)為其自身的next節(jié)點(diǎn)，并且令指定節(jié)點(diǎn)
          的prev節(jié)點(diǎn)為null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        
        //同理，如果指定節(jié)點(diǎn)的下一個節(jié)點(diǎn)為null，代表指定節(jié)點(diǎn)為尾節(jié)點(diǎn)，令
          尾節(jié)點(diǎn)等于指定節(jié)點(diǎn)的上一個節(jié)點(diǎn)，否則，指定節(jié)點(diǎn)的next節(jié)點(diǎn)的prev節(jié)點(diǎn)
          等于其自身的prev節(jié)點(diǎn)，且令自身的next節(jié)點(diǎn)等于null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //最后，將指定節(jié)點(diǎn)的item也置為null，防止內(nèi)存泄漏
        x.item = null;
        size--;
        modCount++;
        return element;
    }
//按照索引值與對應(yīng)集合類進(jìn)行批量添加
public boolean addAll(int index, Collection c) {
        //檢驗(yàn)index是否合法，就是檢查其是否在[0,size]范圍內(nèi)，如果index為size，就是尾節(jié)點(diǎn)
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //如果集合類長度為0，那么直接返回失敗
        if (numNew == 0)
            return false;
        
        //如果index與size大小相等，直接設(shè)置插入位置為尾節(jié)點(diǎn)
          ，否則，進(jìn)行遍歷查找節(jié)點(diǎn)，設(shè)置查找到的節(jié)點(diǎn)的前一個節(jié)點(diǎn)為插入節(jié)點(diǎn)
        Node pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        
        //循環(huán)插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);
            //如果pred==null，代表index=0，此時直接插入首節(jié)點(diǎn)，令
              首節(jié)點(diǎn)等于新節(jié)點(diǎn)，否則，直接令pred的下一個節(jié)點(diǎn)為新節(jié)點(diǎn)，然后依序插入
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        //如果，succ==null，代表index==size，則是直接從
          尾部進(jìn)行插入，所以，直接令尾節(jié)點(diǎn)指向插入的最后一個節(jié)點(diǎn)即可
          ，否則，令最后一個插入節(jié)點(diǎn)的next等于succ，
          令succ的prev等于最后一個插入節(jié)點(diǎn)即可（其實(shí)就是進(jìn)行了一個銜接）
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        //對元素數(shù)量進(jìn)行增加
        size += numNew;
        modCount++;
        return true;
    }
//根據(jù)索引查找對應(yīng)的節(jié)點(diǎn)（調(diào)用這個方法的方法已經(jīng)判斷過index，所以直接使用）
Node node(int index) {
        //如果index靠近左邊，從first開始遍歷，否則，從last開始遍歷
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }