java.util.LinkedList源码阅读

LinkedList 是链表实现的线性表（双链表），元素有序且可以重复。

LinkedList继承AbstractSequentialList并且实现了List和Deque，Cloneable, Serializable接口。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

1.属性

//链表元素的个数
transient int size = 0;
//第一个元素的指针
transient Node<E> first;
//最后一个元素的指针
transient Node<E> last;

Node 类，这是 LinkedList 类中的一个内部类，集合里每一个元素就代表一个 Node 类对象，LinkedList 集合就是由许多个 Node 对象类似于手拉着手构成，由此可知，LinkedList是一个双向链表。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            //存放数据
            this.item = element;
            //该节点上一节点的引用
            this.next = next;
            //该节点下一节点的引用
            this.prev = prev;
        }
    }

每个节点都prev都保存上一个节点的引用，next保存下一个节点的引用；

2.构造函数

• 无参构造函数

 public LinkedList() {
    }

• 泛型参数有参构造函数

  public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

3.添加元素

• 添加元素

 public boolean add(E e) {
 //将元素添加到链表的尾部
        linkLast(e);
        return true;
    }

 void linkLast(E e) {
        //用变量将链表的尾节点存储下来
        final Node<E> l = last;

        //新增加一个元素，即新增加一个node节点。该节点prev指向当前last节点，e为添加元素，next指向null
        final Node<E> newNode = new Node<>(l, e, null);

        //将链表尾部指向新节点
        last = newNode;
        
        if (l == null)
        //如果链表为空，将这个新节点也设为头部节点，那么新增节点既是头节点也是尾节点,并且头节点的prev和next都是null
            first = newNode;
        else
        //链表不为空，将之前存储的原链表尾部节点的next指向新增节点
            l.next = newNode;
        //节点数加1
        size++;
        modCount++;
    }

这里只介绍add(E e)，addFirst(E e)，addLast(E e)和 实现类似。

• 将元素插入指定位置

public void add(int index, E element) {
       //判断索引是否越界
        checkPositionIndex(index);

        if (index == size)
        //如果索引值等于链表大小，则直接在链尾添加元素
            linkLast(element);
        else
            linkBefore(element, node(index));
}

//根据索引获取节点，因为是链表，不像数组，在内存中并不是一块连续的位置存储，不能根据索引直接取到值，需要从头部或者尾部一个个向下找
Node<E> node(int index) {
    //size >> 1表示移位，指除以2的1次方
    if (index < (size >> 1)) {//如果索引比链表的一半小
        Node<E> x = first;//设x为头节点,表示从头节点开始遍历
        for (int i = 0; i < index; i++)//因为只需要找到index处，所以遍历到index处就可以停止
            x = x.next;//从第一个节点开始向后移动，直到移动到index前一个节点就能找到index处的节点
        return x;
    } else {//如果索引比链表的一半大
        Node<E> x = last;//设x为尾部节点,表示从最后一格节点开始遍历
        for (int i = size - 1; i > index; i--)
            x = x.prev;//从最后一个节点开始向前移动，直到移动到index后一个节点就能找到index处的节点
        return x;
    }
}

void linkBefore(E e, Node<E> succ) {

        //获取index 节点的上一个节点
        final Node<E> pred = succ.prev;

        //新增一个节点，prev指向pred,e为新加元素，next指向succ节点
        final Node<E> newNode = new Node<>(pred, e, succ);

        //succ的prev指向新节点
        succ.prev = newNode;

        //如果插入节点的上一个节点引用为空
        if (pred == null)

        //头部节点设为新节点
            first = newNode;
        else
        //原始index的上一个节点的next 设为新节点
            pred.next = newNode;
        //链表长度+1
        size++;
        modCount++;
}

4.修改元素

public E set(int index, E element) {
    //判断索引是否越界
    checkElementIndex(index);
    Node<E> x = node(index);//获取指定索引处的节点
    E oldVal = x.item;//获取指定索引处节点的实际元素
    x.item = element;//将指定位置的节点元素替换成需要修改的元素
    return oldVal;//返回索引处原来的节点的元素值
}

5.查找元素

public E get(int index) {
    //判断索引是否越界 return index >= 0 && index <= size;
    checkElementIndex(index);
    //node(index)上面已经讲过，这里获取节点的实际元素
    return node(index).item;
}

返回链表中第一个出现指定元素的索引

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {//查找的元素为null
        for (Node<E> x = first; x != null; x = x.next) {//从头结点开始不断向下一个节点进行遍历
            if (x.item == null)
                return index;//找到了则返回index
            index++;
        }
    } else {//查找的元素不为null
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))//使用equals 比较
                return index;//找到了则返回index
            index++;
        }
    }
    return -1;//找不到指定元素，则返回-1
}

6.删除元素

public E remove(int index) {
    checkElementIndex(index);
    //先获取指定位置的节点
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {//如果删除节点的上一个节点引用为null，表示删除节点为头节点
        first = next;//将头节点设置为删除节点的下一个节点
    } else {
        prev.next = next;//将删除节点的上一个节点的next指向删除节点的下一个节点
        x.prev = null;//将删除节点的上一个节点引用设为null，否则链表就乱了
    }

    if (next == null) {//如果删除节点的下一个节点引用为null,表示删除节点为尾部节点
        last = prev;//将尾部节点设为删除节点的上一个节点
    } else {//不是尾部节点
        next.prev = prev;//将删除节点的下一个节点的prev指向删除节点的上一个节点
        x.next = null;//将删除节点的下一个节点引用设为null
    }

    x.item = null;//将删除节点的实际元素设为null,便于垃圾回收
    size--;
    modCount++;
    return element;
}