LinkedList部分源码解析

LinkedList源码解读
链表是一个有序集合（orderd collection），每个对象的位置十分重要。
Node first;//元素前一个节点
Node first;//元素后一个节点

---

将对象e添加到链表，添加成功则返回true

 public boolean add(E e) {//此方法是将对象加到链表尾部
        linkLast(e);//将对象添加到链表的尾部
        return true;
    }

 void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);//实例化节点对象，在表的last之后
        last = newNode;
        if (l == null)//如果last节点为空，说明链表为空，此时将要添加的元素直接赋给表头first
            first = newNode;
        else
            l.next = newNode;//链表不为空，则将要添加的节点放在表尾
        size++;
        modCount++;
    }

---

将元素element添加到指定位置index

public void add(int index, E element) {
        checkPositionIndex(index);//检查位置是否合理，不合理则抛异常

        if (index == size)//如果要插入位置就是表的最后一个位置
            linkLast(element);
        else
            linkBefore(element, node(index));//否则，添加到原index位置的节点之前
    }

    //将元素e放在succ节点之前
     void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;//得到succ原前一个元素pred
        final Node<E> newNode = new Node<>(pred, e, succ);//e插在pred和succ之间
        succ.prev = newNode;//succ前指针previous指向新添元素
        if (pred == null)//如果pred为空即succ是原链表的头，则新加入元素为新的表头
            first = newNode;
        else
            pred.next = newNode;//否则pred后指针next指向新添元素
        size++;
        modCount++;
    }

    //获得链表指定位置index的节点node
      Node<E> node(int index) {

        if (index < (size >> 1)) {//如果指定位置小于链表的一半size/2，则从表头first逐一遍历，直到index位置
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {//如果指定位置大于链表的一半size/2，则从表尾last逐一遍历，直到index位置
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

以上代码用图表示为

如果链表有n个元素，有n+1个位置可以添加新元素
|ABC
A|BC
AB|C
ABC|