全局变量

/*LinkedList size*/transient int size = 0;    /**     * Pointer to first node.当前链头     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node
    
      first;    /**     * Pointer to last node.当前链尾     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node
     
       last;
     
    

构造函数

public LinkedList() {    }//Collection集合转成LinkedList    public LinkedList(Collection
     c) {        this();        addAll(c);   }

addAll Collection集合添加至LinkedList

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

addAll 指定下标Collection集合添加至LinkedList

public boolean addAll(int index, Collection
     c){        checkPositionIndex(index);//检查index是否超过size        Object[] a = c.toArray();        int numNew = a.length;        //Collection本身为空集合则直接返回false        if (numNew == 0)            return false;        //定义上个节点,成功节点        Node
    
      pred, succ;        //如果从链尾添加则链尾Last为pred,succ为null        if (index == size) {            succ = null;            pred = last;        } else {            //否则获取index所在Node节点,指向succ            succ = node(index);            //获取succ的上个节点指向pred            pred = succ.prev;        }        //迭代Collection的数组        for (Object o : a) {            @SuppressWarnings("unchecked")            E e = (E) o;            //创建新节点,并完成(pred<-e)左链关系            Node
     
       newNode = new Node<>(pred, e, null);            //如果上个节点为空则newNode指向链头            if (pred == null)                first = newNode;            //否则完成(pred<=>e)双向链表                else                pred.next = newNode;            //重置pred,令新节点newNode指向pred,然后继续迭代            pred = newNode;        }        //链尾添加则将迭代完的pred指向last            if (succ == null) {            last = pred;        } else {            //否则建立双向链表pred<=>succ            pred.next = succ;            succ.prev = pred;        }        //更新size        size += numNew;        modCount++;        return true;    }
     
    

linkFirst 将E添加至链表头

private void linkFirst(E e) {        //备份原首元素至f        final Node
    
      f = first;        //构造newNode,并指向为当前链表头first        final Node
     
       newNode = new Node<>(null, e, f);        first = newNode;        //如果原首元素为空,则newNode也是链表尾        if (f == null)            last = newNode;        else        //否则建立双向链关系 f<=>newNode            f.prev = newNode;        size++;        modCount++;    }
     
    

linkFirst 将E添加至链表尾

void linkLast(E e) {        //备份尾元素        final Node
    
      l = last;        //新建节点并完成单相关系l <= newNode        final Node
     
       newNode = new Node<>(l, e, null);        //newNode成为新的链表尾        last = newNode;        //原链表尾为空,则newNode将成为新链表头        if (l == null)            first = newNode;        else        //否则建立双向链表关系 l <=> newNode            l.next = newNode;        size++;        modCount++;    }
     
    

linkBefore 将E添加到非空节点succ的前面

void linkBefore(E e, Node
    
      succ) {        // assert succ != null;succ必须非空,否则空指针        //备份succ的上个节点prev        final Node
     
       pred = succ.prev;        //建立新节点,并完成单向链关系pred<-newNode->succ        final Node
      
        newNode = new Node<>(pred, e, succ);        //pred<-newNode<=>succ        succ.prev = newNode;        //pred为空则newNode成为链表头        if (pred == null)            first = newNode;        else        //否则建立双向关系pred<=>newNode<=>succ            pred.next = newNode;        size++;        modCount++;    }
      
     
    

linkBefore 将当前链头first拆除

private E unlinkFirst(Node
    
      f) {        // assert f == first && f != null; //f必须为链表头并且非空        //备份原链头,并用于返回        final E element = f.item;        //获取原链次节点        final Node
     
       next = f.next;        f.item = null;        f.next = null; // help GC        //原表链次节点成为当前链头first        first = next;        //如果原表链次节点为空,则尾也为空        if (next == null)            last = null;        else        //否则至链头的上节点为空            next.prev = null;        size--;        modCount++;        return element;    }
     
    

linkBefore 将当前链尾last拆除

private E unlinkLast(Node
    
      l) {        // assert l == last && l != null;//参数l必须为链尾并且非空        //备份原链尾,并用于返回        final E element = l.item;        //原链尾上节点作为最新链尾last        final Node
     
       prev = l.prev;        l.item = null;        l.prev = null; // help GC        last = prev;        //如果原表链尾二节点为空,则头也为空        if (prev == null)            first = null;        else        //否则至链头的下节点为空            prev.next = null;        size--;        modCount++;        return element;    }
     
    

linkBefore拆除非空节点

E unlink(Node
    
      x) {        // assert x != null;//目标节点必须不为空        final E element = x.item;        final Node
     
       next = x.next;        final Node
      
        prev = x.prev;        //目标节点的上节点prev为空,即目标节点为链表头,所以next就成为链头        if (prev == null) {            first = next;        } else {        //否则为建立单向关系prev->next             prev.next = next;            x.prev = null;//拆除原节点prev关系        }    //目标节点的下节点next为空,即目标节点为链表尾,所以prev就成为链尾        if (next == null) {            last = prev;        } else {         //否则为建立双向关系prev<=>next             next.prev = prev;            x.next = null;//拆除原节点next关系        }        //除原节点item置空,help gc        x.item = null;        size--;        modCount++;        return element;    }
      
     
    

getFirst获取首节点元素

public E getFirst() {        final Node
    
      f = first;        if (f == null)            throw new NoSuchElementException();        return f.item;    }
    

getFirst获取尾节点元素

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

removeFirst移除头节点元素

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

removeLast移除尾节点元素

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

contains是否包含此元素

public boolean contains(Object o) {        return indexOf(o) != -1;    }

indexOf() 元素o所在链表下标

public int indexOf(Object o) {        int index = 0;        //o为空则迭代判断出首空元素,并返回下标        if (o == null) {            for (Node
    
      x = first; x != null; x = x.next) {                if (x.item == null)                    return index;                index++;            }        } else {        o非空则迭代判断equals一致对象,并返回下标            for (Node
     
       x = first; x != null; x = x.next) {                if (o.equals(x.item))                    return index;                index++;            }        }        return -1;    }
     
    

indexOf() 元素o所在链表最后下标

public int lastIndexOf(Object o) {        int index = size;        if (o == null) {            //反向迭代            //o为空则迭代判断出最后空元素,并返回下            for (Node
    
      x = last; x != null; x = x.prev) {                index--;                if (x.item == null)                    return index;            }        } else {            //o非空则迭代判断equals最后一致对象,并返回下标            for (Node
     
       x = last; x != null; x = x.prev) {                index--;                if (o.equals(x.item))                    return index;            }        }        return -1;    }
     
    

iremoveFirstOccurrence 移除首个元素o

public boolean removeFirstOccurrence(Object o) {        return remove(o);    }

remove 移除首个元素o

public boolean remove(Object o) {        if (o == null) {            //迭代出首空元素并完成拆链            for (Node
    
      x = first; x != null; x = x.next) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            //迭代出首元素并完成拆链            for (Node
     
       x = first; x != null; x = x.next) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }
     
    

clear 清空链

public void clear() {        // Clearing all of the links between nodes is "unnecessary", but:        // - helps a generational GC if the discarded nodes inhabit        //   more than one generation        // - is sure to free memory even if there is a reachable Iterator        //迭代完成拆链        for (Node
    
      x = first; x != null; ) {            Node
     
       next = x.next;            x.item = null;            x.next = null;            x.prev = null;            x = next;        }        first = last = null;        size = 0;        modCount++;    }
     
    

get 获取所在下标元素

public E get(int index) {        checkElementIndex(index);//判断下标不能超过size        return node(index).item;    }

node 获取所在下标元素

Node
    
      node(int index) {        // assert isElementIndex(index); 判断下标不能超过size        //判断index实在链前半还是链后半,选择正向还是反向迭代        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;        }    }
      
     
    

removeLastOccurrence 拆除最后一个o所在链

//都是反向迭代，分null和equals   public boolean removeLastOccurrence(Object o) {        if (o == null) {            for (Node
    
      x = last; x != null; x = x.prev) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            for (Node
     
       x = last; x != null; x = x.prev) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }
     
    

jdk7相关