LinkedList源码解析（一）

摘要：基本属性存储数据量指向第一个节点的指针指向最后一个节点的指针。

     transient int size = 0;//存储数据量

    /**
     * Pointer to first node.
     */
    transient Node first;//指向第一个节点的指针

    /**
     * Pointer to last node.
     */
    transient Node last;//指向最后一个节点的指针。

private static class Node {
        E item;
        Node next;//下一个节点
        Node prev;//上一个节点

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

LinkedList(Collection c)构造方法

 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);//下标在范围内

        Object[] a = c.toArray();//转化为对象数组
        int numNew = a.length;
        if (numNew == 0)
            return false;//长度为0直接返回false

        Node pred, succ;
        if (index == size) {//如果是尾插入
            succ = null;//下一个节点：设置成null
            pred = last;//上一个节点：设置成last
        } else {//如果是中部插入
            succ = node(index);//下一个节点：获取指定索引的节点
            pred = succ.prev;//上一个节点：指定索引节点的上一个节点
        }

        for (Object o : a) {//循环对象数组
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);//构造方法（前一个节点，数据，下一个节点）
            if (pred == null)//如果pre为空说明集合没有数据
                first = newNode;//那么第一个节点指针指向newNode
            else
                pred.next = newNode;//前一个节点（上一次循环的newNode）的next设置为newNode
                
            pred = newNode;//把pre设置成newNode供下一次循环使用
        }

        if (succ == null) {//如果是尾插入
            last = pred;//把指向最后一个节点的指针设置成pred，即设置成，最后一个newNode
        } else {//如果不是尾插入
            pred.next = succ;//newNode的next变成suc
            succ.prev = pred;//next的pre变成newNode
        }

        size += numNew;//修改存储长度
        modCount++;
        return true;
    }

node(int index)返回指定元素索引处的（非null）节点

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

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

linkFirst(E e)把e放置到链表开头

 private void linkFirst(E e) {
        final Node f = first;//获取第一个节点
        final Node newNode = new Node<>(null, e, f);//创建一个新的节点，并设置下一个节点为原来的第一个节点
        first = newNode;//第一个节点设置成newNode 
        if (f == null)//原本第一个节点为空，即链表是空的
            last = newNode;//设置最后一个节点设置成newNode
        else
            f.prev = newNode;//否则原本第一个节点的上一个节点设置成newNode
        size++;
        modCount++;
    }

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

void linkLast(E e) {
        final Node l = last;//获取最后的节点
        final Node newNode = new Node<>(l, e, null);//创建一个新的节点并设置上一个节点为原来的最后一个节点
        last = newNode;//最后一个节点设置成newNode
        if (l == null)//如果原本最后节点为空的，即链表是空的
            first = newNode;//设置第一个节点为newNode
            第一个节点为
        else
            l.next = newNode;//否则原来最后一个节点的下一个节点变成newNode
        size++;
        modCount++;
    }

linkBefore(E e, Node succ)在节点succ前插入e

 void linkBefore(E e, Node succ) {
        // assert succ != null;  断言succ不是空的
        final Node pred = succ.prev;//获取succ的上一个节点
        final Node newNode = new Node<>(pred, e, succ);//新建一个节点，设置上一个节点为pred，下一个节点为succ
        succ.prev = newNode;//succ的上一个节点设置为newNode
        if (pred == null)//如果succ是第一个节点
            first = newNode;//第一个节点指针指向newNode
        else
            pred.next = newNode;//否则succ上一个节点的next设置成newNode
        size++;//数据量加1
        modCount++;
    }

unlinkFirst(Node f)取消第一个节点

 private E unlinkFirst(Node f) {
        // assert f == first && f != null;断言f是首节点，并且f不是空的
        final E element = f.item;//获取第一个节点的数据
        final Node next = f.next;//获取第一个节点的next
        f.item = null;//第一个节点数据置空
        f.next = null; //第一个节点的next置空，取消无效的引用帮助gc
        first = next;//第一个节点的指针指向next
        if (next == null)//如果是唯一的节点
            last = null;//最后一个节点的指针也置空
        else
            next.prev = null;//否则下一个节点的prev置空，（由于成为新的第一个节点，第一个节点没有pre）
        size--;//数据量减1
        modCount++;
        return element;//返回取消的数据
    }

unlinkLast(Node l)取消最后一个节点

private E unlinkLast(Node l) {
        // assert l == last && l != null;断言l是最后一个节点，并且l不是空的
        final E element = l.item;//获取最后一个节点的数据
        final Node prev = l.prev;//获取最后一个节点的prev
        l.item = null;//最后一个节点的数据置空
        l.prev = null; //最后一个节点的pre数据置空，取消无效的引用帮助gc
        last = prev;//最后一个节点指针指向prev
        if (prev == null)//如果是唯一的节点
            first = null;//第一个节点的指针也置空
        else
            prev.next = null;//否则上一个节点的next置空，（由于成为新的最后一个节点，最后一个节点没有next）
        size--;//数据量减1
        modCount++;
        return element;//返回取消的数据
    }

unlink(Node x)取消某一个节点

E unlink(Node x) {
        // assert x != null;断言节点x不是空的
        final E element = x.item;//获取节点值
        final Node next = x.next;//获取节点的next
        final Node prev = x.prev;//获取节点的pre

        if (prev == null) {//如果x是首节点
            first = next;//first指向next
        } else {//x不是首节点
            prev.next = next;//否则上一个节点next指向下一个节点
            x.prev = null;//x的上一个节点引用置空
        }

        if (next == null) {//如果x是尾节点
            last = prev;//last的指针指向pre
        } else {//x不是尾节点
            next.prev = prev;//下一个节点的pre指向上一个节点
            x.next = null;//下一个节点的引用置空
        }

        x.item = null;//x的值置空
        size--;//数据量减1
        modCount++;
        return element;//返回移除的数据
    }

getFirst()获取第一个节点的值

public E getFirst() {
        final Node f = first;
        if (f == null)//空的集合
            throw new NoSuchElementException();
        return f.item;//返回第一个节点指针，指向节点，包含的值
    }

getLast()返回最后一个节点的值

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

addFirst(E e)在第一个节点指针，指向节点的，前面插入节点e

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

addLast(E e)在第最后一个节点指针，指向节点的，后面插入节点e

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

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

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

indexOf(Object o)返回指定元素第一次出现的索引

public int indexOf(Object o) {
        int index = 0;//初始索引下标0
        if (o == null) {//o为空的时候
            for (Node x = first; x != null; x = x.next) {//从第一个节点指针指向的节点循环到最后一个节点（最后一个节点指针last指向的节点的next是null）
                if (x.item == null)//直接对比内存地址
                    return index;//对等返回index
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {//从第一个节点指针指向的节点循环到最后一个节点（最后一个节点指针last指向的节点的next是null）
                if (o.equals(x.item))//调用o的equals方法
                    return index;//对等返回index
                index++;
            }
        }
        return -1;//没有找到返回-1
    }