摘要：基本屬性存儲數(shù)據(jù)量指向第一個節(jié)點的指針指向最后一個節(jié)點的指針。

     transient int size = 0;//存儲數(shù)據(jù)量

    /**
     * Pointer to first node.
     */
    transient Node first;//指向第一個節(jié)點的指針

    /**
     * Pointer to last node.
     */
    transient Node last;//指向最后一個節(jié)點的指針。

private static class Node {
        E item;
        Node next;//下一個節(jié)點
        Node prev;//上一個節(jié)點

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

LinkedList(Collection c)構(gòu)造方法

 public LinkedList(Collection c) {
        this();
        addAll(c);
    }

addAll(Collection c)將指定集合中的所有元素追加到末尾

public boolean addAll(Collection c) {
        return addAll(size, c);
    }

addAll(int index, Collection c)將指定集合中的所有元素，插入到指定索引處

 public boolean addAll(int index, Collection c) {
        checkPositionIndex(index);//下標在范圍內(nèi)

        Object[] a = c.toArray();//轉(zhuǎn)化為對象數(shù)組
        int numNew = a.length;
        if (numNew == 0)
            return false;//長度為0直接返回false

        Node pred, succ;
        if (index == size) {//如果是尾插入
            succ = null;//下一個節(jié)點：設置成null
            pred = last;//上一個節(jié)點：設置成last
        } else {//如果是中部插入
            succ = node(index);//下一個節(jié)點：獲取指定索引的節(jié)點
            pred = succ.prev;//上一個節(jié)點：指定索引節(jié)點的上一個節(jié)點
        }

        for (Object o : a) {//循環(huán)對象數(shù)組
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);//構(gòu)造方法（前一個節(jié)點，數(shù)據(jù)，下一個節(jié)點）
            if (pred == null)//如果pre為空說明集合沒有數(shù)據(jù)
                first = newNode;//那么第一個節(jié)點指針指向newNode
            else
                pred.next = newNode;//前一個節(jié)點（上一次循環(huán)的newNode）的next設置為newNode
                
            pred = newNode;//把pre設置成newNode供下一次循環(huán)使用
        }

        if (succ == null) {//如果是尾插入
            last = pred;//把指向最后一個節(jié)點的指針設置成pred，即設置成，最后一個newNode
        } else {//如果不是尾插入
            pred.next = succ;//newNode的next變成suc
            succ.prev = pred;//next的pre變成newNode
        }

        size += numNew;//修改存儲長度
        modCount++;
        return true;
    }

node(int index)返回指定元素索引處的（非null）節(jié)點

Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {//小于一半
            Node x = first;
            for (int i = 0; i < index; i++)//從0往后循環(huán)到index
                x = x.next;
            return x;
        } else {//大于一半
            Node x = last;
            for (int i = size - 1; i > index; i--)//從size往前循環(huán)到index
                x = x.prev;
            return x;
        }
    }

linkFirst(E e)把e放置到鏈表開頭

 private void linkFirst(E e) {
        final Node f = first;//獲取第一個節(jié)點
        final Node newNode = new Node<>(null, e, f);//創(chuàng)建一個新的節(jié)點，并設置下一個節(jié)點為原來的第一個節(jié)點
        first = newNode;//第一個節(jié)點設置成newNode 
        if (f == null)//原本第一個節(jié)點為空，即鏈表是空的
            last = newNode;//設置最后一個節(jié)點設置成newNode
        else
            f.prev = newNode;//否則原本第一個節(jié)點的上一個節(jié)點設置成newNode
        size++;
        modCount++;
    }

linkLast(E e)把e放在鏈表末尾

void linkLast(E e) {
        final Node l = last;//獲取最后的節(jié)點
        final Node newNode = new Node<>(l, e, null);//創(chuàng)建一個新的節(jié)點并設置上一個節(jié)點為原來的最后一個節(jié)點
        last = newNode;//最后一個節(jié)點設置成newNode
        if (l == null)//如果原本最后節(jié)點為空的，即鏈表是空的
            first = newNode;//設置第一個節(jié)點為newNode
            第一個節(jié)點為
        else
            l.next = newNode;//否則原來最后一個節(jié)點的下一個節(jié)點變成newNode
        size++;
        modCount++;
    }

linkBefore(E e, Node succ)在節(jié)點succ前插入e

 void linkBefore(E e, Node succ) {
        // assert succ != null;  斷言succ不是空的
        final Node pred = succ.prev;//獲取succ的上一個節(jié)點
        final Node newNode = new Node<>(pred, e, succ);//新建一個節(jié)點，設置上一個節(jié)點為pred，下一個節(jié)點為succ
        succ.prev = newNode;//succ的上一個節(jié)點設置為newNode
        if (pred == null)//如果succ是第一個節(jié)點
            first = newNode;//第一個節(jié)點指針指向newNode
        else
            pred.next = newNode;//否則succ上一個節(jié)點的next設置成newNode
        size++;//數(shù)據(jù)量加1
        modCount++;
    }

unlinkFirst(Node f)取消第一個節(jié)點

 private E unlinkFirst(Node f) {
        // assert f == first && f != null;斷言f是首節(jié)點，并且f不是空的
        final E element = f.item;//獲取第一個節(jié)點的數(shù)據(jù)
        final Node next = f.next;//獲取第一個節(jié)點的next
        f.item = null;//第一個節(jié)點數(shù)據(jù)置空
        f.next = null; //第一個節(jié)點的next置空，取消無效的引用幫助gc
        first = next;//第一個節(jié)點的指針指向next
        if (next == null)//如果是唯一的節(jié)點
            last = null;//最后一個節(jié)點的指針也置空
        else
            next.prev = null;//否則下一個節(jié)點的prev置空，（由于成為新的第一個節(jié)點，第一個節(jié)點沒有pre）
        size--;//數(shù)據(jù)量減1
        modCount++;
        return element;//返回取消的數(shù)據(jù)
    }

unlinkLast(Node l)取消最后一個節(jié)點

private E unlinkLast(Node l) {
        // assert l == last && l != null;斷言l是最后一個節(jié)點，并且l不是空的
        final E element = l.item;//獲取最后一個節(jié)點的數(shù)據(jù)
        final Node prev = l.prev;//獲取最后一個節(jié)點的prev
        l.item = null;//最后一個節(jié)點的數(shù)據(jù)置空
        l.prev = null; //最后一個節(jié)點的pre數(shù)據(jù)置空，取消無效的引用幫助gc
        last = prev;//最后一個節(jié)點指針指向prev
        if (prev == null)//如果是唯一的節(jié)點
            first = null;//第一個節(jié)點的指針也置空
        else
            prev.next = null;//否則上一個節(jié)點的next置空，（由于成為新的最后一個節(jié)點，最后一個節(jié)點沒有next）
        size--;//數(shù)據(jù)量減1
        modCount++;
        return element;//返回取消的數(shù)據(jù)
    }

unlink(Node x)取消某一個節(jié)點

E unlink(Node x) {
        // assert x != null;斷言節(jié)點x不是空的
        final E element = x.item;//獲取節(jié)點值
        final Node next = x.next;//獲取節(jié)點的next
        final Node prev = x.prev;//獲取節(jié)點的pre

        if (prev == null) {//如果x是首節(jié)點
            first = next;//first指向next
        } else {//x不是首節(jié)點
            prev.next = next;//否則上一個節(jié)點next指向下一個節(jié)點
            x.prev = null;//x的上一個節(jié)點引用置空
        }

        if (next == null) {//如果x是尾節(jié)點
            last = prev;//last的指針指向pre
        } else {//x不是尾節(jié)點
            next.prev = prev;//下一個節(jié)點的pre指向上一個節(jié)點
            x.next = null;//下一個節(jié)點的引用置空
        }

        x.item = null;//x的值置空
        size--;//數(shù)據(jù)量減1
        modCount++;
        return element;//返回移除的數(shù)據(jù)
    }

getFirst()獲取第一個節(jié)點的值

public E getFirst() {
        final Node f = first;
        if (f == null)//空的集合
            throw new NoSuchElementException();
        return f.item;//返回第一個節(jié)點指針，指向節(jié)點，包含的值
    }

getLast()返回最后一個節(jié)點的值

public E getLast() {
        final Node l = last;
        if (l == null)//空的集合
            throw new NoSuchElementException();
        return l.item;
    }

removeFirst()刪除第一個節(jié)點指針，指向的節(jié)點

 public E removeFirst() {
        final Node f = first;
        if (f == null)//空的集合
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

removeLast()刪除最后一個節(jié)點指針，指向的節(jié)點

 public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

addFirst(E e)在第一個節(jié)點指針，指向節(jié)點的，前面插入節(jié)點e

  public void addFirst(E e) {
        linkFirst(e);
    }

addLast(E e)在第最后一個節(jié)點指針，指向節(jié)點的，后面插入節(jié)點e

  public void addLast(E e) {
        linkLast(e);
    }

contains(Object o)查看集合是否存在對象o

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

indexOf(Object o)返回指定元素第一次出現(xiàn)的索引

public int indexOf(Object o) {
        int index = 0;//初始索引下標0
        if (o == null) {//o為空的時候
            for (Node x = first; x != null; x = x.next) {//從第一個節(jié)點指針指向的節(jié)點循環(huán)到最后一個節(jié)點（最后一個節(jié)點指針last指向的節(jié)點的next是null）
                if (x.item == null)//直接對比內(nèi)存地址
                    return index;//對等返回index
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {//從第一個節(jié)點指針指向的節(jié)點循環(huán)到最后一個節(jié)點（最后一個節(jié)點指針last指向的節(jié)點的next是null）
                if (o.equals(x.item))//調(diào)用o的equals方法
                    return index;//對等返回index
                index++;
            }
        }
        return -1;//沒有找到返回-1
    }