Java集合——LinkedList源码

关键源码（jdk1.7和jdk1.8相同）

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    // 有效个数
    transient int size = 0;

    // 头结点
    transient Node first;

    // 尾节点
    transient Node last;

    // 默认构造器
    public linkedList() {
    }

    // add方法，插入到链表的尾部
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    // get方法
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    // 查找下标index所在的元素，分两边找：小于一半的从头部开始找；大于一半的从尾部开始找。
    Node node(int 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;
        }
    }