源码分析之LinkedList

在leetcode中遇到了一道设计链表的题，要求中有一点是不能使用内置的LinkedList库，于是在自己实现了简易版的链表之后，找到了内置的源码来做个分析。
可以自行选择实现单向或双向链表 原题链接。
首先，LinkedList是个双向链表，每个数据结点中都有两个“指针”，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点（百科）。
首先，来看看LinkedList的基础属性：

public class LinkedList<E>  extends AbstractSequentialList<E>  implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
    transient int size = 0; //节点个数
	transient Node<E> first; //首节点
    transient Node<E> last;  //尾节点
    public LinkedList() {  //初始化一个空的链表集合
    }  
 
    public LinkedList(Collection<? extends E> c) {  //根据已有集合初始化
        this();  
        addAll(c);  //稍后分析addAll
    }
    //内部类---节点
    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;  
	    }  
	}
 }

节点的添加

//默认的add会加到尾部
public boolean add(E e) {  
    linkLast(e);  
    return true;  
}
//指定位置添加
public void add(int index, E element) {  
    checkPositionIndex(index); //检查节点是否存在
    
    if (index == size)  
        linkLast(element);  //在节点尾部添加
    else  
	    linkBefore(element, node(index));  //在指定节点前添加，node(index)会查询出位于index位置的节点
}
public void addFirst(E e) {  
    linkFirst(e);  
}
public void addLast(E e) {  
    linkLast(e);  
}

1.检查节点是否存在（方法很简单，判断了下size和index）:

private void checkPositionIndex(int index) {  
    if (!isPositionIndex(index))  //isPositionIndex
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
}
private boolean isPositionIndex(int index) {  
    return index >= 0 && index <= size;  
}

2.在节点尾部/首部添加：

//在首部添加节点，此方法为私有方法，实际使用时调用addFirst
private void linkFirst(E e) {  
    final Node<E> f = first;  //将final类型的f节点指向首节点
    final Node<E> newNode = new Node<>(null, e, f);  //新建节点
    first = newNode;  //将新节点变为首节点
    if (f == null)  
        last = newNode;  //链表为空，此时first = last = newNode
    else  
	    f.prev = newNode;  //将新节点加入到链表中
    size++;  //节点数+1
    modCount++; //modCount表示更改次数，在遍历时才会用到
}

//在尾部添加节点，此方法没有修饰符
void linkLast(E e) {  
    final Node<E> l = last;  
    final Node<E> newNode = new Node<>(l, e, null);  
    last = newNode;  
    if (l == null)   
        first = newNode;  
    else  
	    l.next = newNode;  
    size++;  
    modCount++;  
}

linkFirst与linkLast类似，这里介绍简单说下linkFirst，首先将当前的首节点的引用赋值给f，然后新建一个Node节点，节点的next指向f，prev为null。将新节点变为首节点，同时判断f是否为空，如果f为空说明链表为空，此时新节点既为首节点也为尾节点，否则将f的prev指向新的节点。此时新节点就加到了链表中。
3.在指定位置添加:

//先看下node(index)如何定位到节点
Node<E> node(int index) {  
  //这里的移位操作size>>1其实就是size的一半，如果index小于size的一半，那么从前往后找，否则从后往前找，这样可以加快查找速度
  if (index < (size >> 1)) {   
        Node<E> x = first;  
        for (int i = 0; i < index; i++) 
            x = x.next;  
        return x;  
    } else {  
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)  
            x = x.prev;  
        return x;  
    }  
}
//在指定节点前添加
void linkBefore(E e, Node<E> succ) {  
    final Node<E> pred = succ.prev;  //拿到指定节点的前一个
    final Node<E> newNode = new Node<>(pred, e, succ);  //新的节点next指向succ，pre指向pred
    succ.prev = newNode;  
    if (pred == null)  
        first = newNode;  //pred为空的话，表示succ为first，将first替换为newNode
    else  
	    pred.next = newNode;  //否则pred的next指向newNode
    size++;  
    modCount++;  
}

构造方法addAll

public boolean addAll(Collection<? extends E> c) {  
    return addAll(size, c); //传入当前size 和构造参数
}
//在指定位置index的前方，添加多个节点
public boolean addAll(int index, Collection<? extends E> c) {  
    checkPositionIndex(index);  
  
    Object[] a = c.toArray();  
    int numNew = a.length;  //需要添加的元素个数
    if (numNew == 0)  
        return false;  
  
    Node<E> pred, succ;  
    if (index == size) {  //位置等于size，即在链表末尾添加，否则在链表中间添加
        succ = null;  
        pred = last;  
    } else {  
        succ = node(index);  //index处的节点
        pred = succ.prev;  //index的上一个节点
    }  

    for (Object o : a) {  
        @SuppressWarnings("unchecked") E e = (E) o;  
        Node<E> newNode = new Node<>(pred, e, null);  //创建新节点
        if (pred == null)  
            first = newNode;  //初始化第一个节点
        else  
		    pred.next = newNode;  //链接新节点
        pred = newNode;  
    }  
    
    if (succ == null) {  
        last = pred;  //在尾部插入，那么循环结束后，pred就是尾节点
    } else {  
        pred.next = succ;  //否则，需要将pred的next指向succ节点
        succ.prev = pred;  
    }  
  
    size += numNew;  //修改节点个数
    modCount++;  
    return true;  
}

节点的删除
删除操作有多种方式，但都是基于unlink方法实现的，这里就简单写一种吧(偷懒ing):

public E remove(int index) {  
    checkElementIndex(index);  //检查是否存在元素
    return unlink(node(index));  //执行unlink
}

//unlink操作
E unlink(Node<E> x) {  
    final E element = x.item;  //需要删除的节点赋给final的element常量
    final Node<E> next = x.next;  
    final Node<E> prev = x.prev;  
  
    if (prev == null) {  
        first = next;  //需要删除的节点为first，那么删除后它next变为first
    } else {  
        prev.next = next;  //前后节点相连，跳过当前节点
        x.prev = null;  //把需要删除节点的pre变为null
    }  
  
    if (next == null) {  
        last = prev;  //需要删除的节点为last，删除后它的pre变为last
    } else {  
        next.prev = prev;  //前后节点相连，跳过当前节点
        x.next = null;  //把需要删除节点的next也变为null
    }  
 
    x.item = null;  //将节点的item也变为null，帮助gc回收
    size--;  //节点数-1
    modCount++;  
    return element;  //返回element
}

节点的查找

//get方法还是调用的node(index)进行定位，返回节点的item
public E get(int index) {  
    checkElementIndex(index);  
    return node(index).item;  
}

到这里，LinkedList的基础方法就分析完了，其余的高级方法诸如push、pop、peek、poll等等，都是基于这些基本方法完成的。（java中的栈是基于Vector实现的，每个方法都有Syncronized修饰，所以在1.5之后LinkedList添加了用于实现无锁栈的方法）

public void push(E e) {  
    addFirst(e);  
}
public E pop() {  
    return removeFirst();  
}
//前两个为空会抛出异常，peek和poll不会
public E peek() {  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
}
public E poll() {  
    final Node<E> f = first;  
    return (f == null) ? null : unlinkFirst(f);  
}

补充： 在源码中可以看到transient和final关键字的使用，这里也把两者的作用记下。

transient的作用：

• 阻止实例中那些用此关键字修饰的变量序列化；当对象被反序列化时，被transient修饰的变量值不会被持久化和恢复。transient只能修饰变量，不能修饰类和方法。

final关键字的一些总结：

• 1.对于一个变量，如果是基本数据类型的变量，则其数值一旦在初始化之后便不能修改，如果是引用类型的变量，则在对其初始化之后便不能再让其指向另外一个对象。
• 2.当用final修饰一个类时，表明这个类不能被继承。final类中的所有成员方法都会隐式地指定为final方法。
• 3.使用final方法的原因有两个。第一个原因是把方法锁定，以防任何继承类修改它的含义；第二个原因是效率。类中所有的private方法都隐式地指定为final。在早期的java版本中，会将final方法转为内嵌调用。但如果方法过于庞大，可能看不到内嵌调用带来的任何性能提升（现版本已经不需要使用final方法进行这些优化了）。