LinkedList源码分析

分析完Arraylist后来看一下List的另一种实现LinkedList。LinkedList底层使用的是双向链表结构，内部类定义了节点结构，一个头结点和尾节点表示队列的开始和结尾。与ArrayList不同的是，LinkedList除了实现了List接口外，还实现了Deque接口，而Deque接口继承自Queue接口，也就是说，LinkedList还可以用来实现双端队列。

关于具体类对象与接口的关系，我个人的理解就是，一个接口定义了它可以实现的全部功能，比如List接口，定义了add、set等等方法，而具体的类比如ArrayList或LinkedList如果实现了这个接口，就必须实现接口中定义的所有方法，所以ArrayList和LinkedList中肯定实现了List接口中定义的所有方法，但是一个类可以实现多个接口，比如LinkedList还实现了Deque接口，那么它内部肯定也实现了Deque接口定义的所有方法。在使用过程中，一般都是定义一个接口指向具体实例比如List list=new LinkedList(); 这样的意义在于只能调用该接口中定义的方法。虽然LinkedList中实现了其他的方法，但是List类型的引用只能调用该接口中定义的方法。

一、基本属性与构造函数

public class LinkedList<E>  
    extends AbstractSequentialList<E>  
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
      
    //内部类节点，实现双端队列  
    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;  
        }  
    }  
      
    transient int size = 0;//实际元素的个数  
  
    transient Node<E> first;//头节点  
  
    transient Node<E> last;//尾节点  
  
    /* 
     * 构造函数 
     */  
    public LinkedList() {//空List  
    }  
  
    public LinkedList(Collection<? extends E> c) {//包含集合中所有元素  
        this();  
        addAll(c);  
    }  
}

既然是双端队列，首先自己定义了结点，然后用first和last来指向头结点与尾结点。

构造函数中也没有具体实现，因为不需要像ArrayList一样初始化数组什么的。

二、内部操作

由于底层由双向链表实现，所以我们先来看一下它内部的操作，主要包括添加节点与删除节点，这些方法没有重写任何接口，而是内部定义，在重写接口的方法的时候，主要还是调用这些底层的操作来实现的。

1、增加结点

/* 
 * 新加一个节点 
 */  
private void linkFirst(E e) {//添加一个节点到链表头部，考虑头部是否为null两种情况  
    final Node<E> f = first;//先保存当前头节点，final类型不可更改  
    final Node<E> newNode = new Node<>(null, e, f);//新建一个节点，后继节点指向原来的头节点  
    first = newNode;//将新的节点指定为头节点  
    if (f == null)//如果原来头节点为空，即原来链表为空  
        last = newNode;//那么新加入的节点即是头节点也是尾节点  
    else//如果原来链表不为空  
        f.prev = newNode;//将原来头节点的前驱指向新的头节点  
    size++;//元素个数+1  
    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++;  
}  

void linkBefore(E e, Node<E> succ) {//添加一个节点到一个指定的非null节点前面，考虑succ节点的前一个节点是否为null两种情况  
    // 必须保证succ节点是非null的  
    final Node<E> pred = succ.prev;//保存succ节点的前驱节点，final类型不可更改  
    final Node<E> newNode = new Node<>(pred, e, succ);//新建一个节点，指定前驱和后继分别指定pred和succ  
    succ.prev = newNode;//succ的前驱节点指向新建的节点  
    if (pred == null)//如果原来的succ的前驱节点为null，则说明succ为头节点  
        first = newNode;//那么将新节点指定为头节点  
    else//如果succ不是头节点  
        pred.next = newNode;//将pred的后继指向新建的节点  
    size++;//  
    modCount++;  
}

2、删除结点

/* 
 * 去掉一个节点 
 */  
private E unlinkFirst(Node<E> f) {//去掉头节点，并返回，考虑头节点的后继是否为null两种情况  
    //  必须保证f是头节点且非null  
    final E element = f.item;//保存数据域最后将其返回  
    final Node<E> next = f.next;//保存头结点的后继，final类型不可更改  
    f.item = null;//头节点的item和next都置为null  
    f.next = null; // 垃圾回收  
    first = next;//指定新的头节点  
    if (next == null)//如果原来头结点的后继为null，则说明原来只有一个节点  
        last = null;//那么删除该节点后尾节点也应该为null  
    else//如果原来链表中不止一个节点  
        next.prev = null;//那么next节点作为头节点前驱应该为null  
    size--;//  
    modCount++;  
    return element;//  
}  

private E unlinkLast(Node<E> l) {//去掉尾节点，并返回，原理同上  
    // 必须保证l是尾节点且非null  
    final E element = l.item;  
    final Node<E> prev = l.prev;  
    l.item = null;  
    l.prev = null; // help GC  
    last = prev;  
    if (prev == null)  
        first = null;  
    else  
        prev.next = null;  
    size--;  
    modCount++;  
    return element;  
}  

E unlink(Node<E> x) {//去掉一个指定的节点，并返回，考虑该节点是头结点、或是尾节点的情况  
    // 必须保证x是非null  
    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;//前驱指向后继  
        x.prev = null;//前驱置null，垃圾回收  
    }  

    if (next == null) {//与判断头结点原理相同  
        last = prev;//  
    } else {//  
        next.prev = prev;//  
        x.next = null;//  
    }  

    x.item = null;//置null，垃圾回收  
    size--;//  
    modCount++;  
    return element;  
}

注释中可以看到，删除一个节点的前提都是该节点肯定不为null，因为在其他方法调用这些底层方法之前，肯定会先进行判断，然后再调用该方法直接对底层结构进行修改。

三、Deque接口

LinkedList实现了Deque接口，也就是双端队列，我们先来看一下该接口的定义

public interface Deque<E> extends Queue<E> {  
    void addFirst(E e);  
    void addLast(E e);  
    boolean offerFirst(E e);  
    boolean offerLast(E e);  
    E removeFirst();  
    E removeLast();  
    E pollFirst();   
    E pollLast();  
    E getFirst();  
    E getLast();  
    E peekFirst();  
    E peekLast();  
    boolean removeFirstOccurrence(Object o);  
    boolean removeLastOccurrence(Object o);  
    // *** Queue methods ***  
    boolean add(E e);  
    boolean offer(E e);  
    E remove();  
    E poll();  
    E element();  
    E peek();  
    // *** Stack methods ***  
    void push(E e);  
    E pop();  
    // *** Collection methods ***  
    boolean remove(Object o);  
    boolean contains(Object o);  
    public int size();  
    Iterator<E> iterator();  
    Iterator<E> descendingIterator();  
}

它继承自Queue接口，关于Queue接口的方法上面的注释中给出了介绍，在Queue的基础上，它还添加了很多Deque的方法和两个Stack的方法，但是该接口并没有继承Stack接口，此处并不是很明白。

在接口定义中明确指出了哪些方法处于哪些操作，但是在LinkedList的代码中这些方法的继承关系并不是很明确，比如在有些方法前面明确指出了// Deque operations和// Queue operations.但是这些注释下面的方法与Deque接口中定义的并不符合，而且也没有Stack的相关操作的说明。

下面列出了LinkedList类中关于Deque接口的方法。

public E getFirst() {//  
    final Node<E> f = first;  
    if (f == null)  
        throw new NoSuchElementException();  
    return f.item;  
}  

public E getLast() {//  
    final Node<E> l = last;  
    if (l == null)  
        throw new NoSuchElementException();  
    return l.item;  
}  

public E removeFirst() {//  
    final Node<E> f = first;  
    if (f == null)  
        throw new NoSuchElementException();  
    return unlinkFirst(f);  
}  

public E removeLast() {//  
    final Node<E> l = last;  
    if (l == null)  
        throw new NoSuchElementException();  
    return unlinkLast(l);  
}  

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

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


// Queue operations.  
//单相队列，队尾进， 队首出  
public E peek() {//取出但不删除队首元素  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
}  

public E element() {//获取但不删除队首元素  
    return getFirst();  
}  

public E poll() {//取出并删除队首元素  
    final Node<E> f = first;  
    return (f == null) ? null : unlinkFirst(f);  
}  

public E remove() {//取出并删除队首元素  
    return removeFirst();  
}  

public boolean offer(E e) {//添加元素到队尾  
    return add(e);  
}  


// Deque operations  
//双端队列  
public boolean offerFirst(E e) {//队首添加元素  
    addFirst(e);  
    return true;  
}  

public boolean offerLast(E e) {//队尾添加元素  
    addLast(e);  
    return true;  
}  

public E peekFirst() {//获取但不删除队首元素  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
 }  

public E peekLast() {//获取但不删除队尾元素  
    final Node<E> l = last;  
    return (l == null) ? null : l.item;  
}  

public E pollFirst() {//取出并删除队首元素  
    final Node<E> f = first;  
    return (f == null) ? null : unlinkFirst(f);  
}  

public E pollLast() {//取出并删除队尾元素  
    final Node<E> l = last;  
    return (l == null) ? null : unlinkLast(l);  
}  

public boolean removeFirstOccurrence(Object o) {//  
    return remove(o);  
}  

public boolean removeLastOccurrence(Object o) {//  
    if (o == null) {  
        for (Node<E> x = last; x != null; x = x.prev) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = last; x != null; x = x.prev) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}  

// *** Stack methods ***这个注释是我自己加的  
//栈，队首插入，队首取出  
public void push(E e) {//进栈操作  
    addFirst(e);  
}  
public E pop() {//出栈操作，删除并取出  
    return removeFirst();  
}

可以看出，这些方法基本都会调用上面第2节介绍的添加和删除操作，也就是说，这些方法仅仅的实现接口时对外的封装，内部的实现全部都依赖与第2节介绍的对底层数据结构的操作的那几个方法。

四、List接口

接下来这几节是根据源码中的注释进行分类的。注释中把剩下的方法分类为Positional Access Operations、Search Operations下面来看一下分类中对应的方法和实现。

1、Positional Access Operations

对指定位置元素的操作。一般参数中都会指定一个index位置，对该位置的元素进行操作。

// Positional Access Operations  

/* 
 * 对指定位置元素的操作 
 */  
public E get(int index) {//返回指定位置的元素  
    checkElementIndex(index);  
    return node(index).item;  
}  

public E set(int index, E element) {//设置指定位置的元素  
    checkElementIndex(index);  
    Node<E> x = node(index);  
    E oldVal = x.item;  
    x.item = element;  
    return oldVal;  
}  

public void add(int index, E element) {//在指定位置插入元素  
    checkPositionIndex(index);  

    if (index == size)  
        linkLast(element);  
    else  
        linkBefore(element, node(index));  
}  

public E remove(int index) {//删除指定位置的元素  
    checkElementIndex(index);  
    return unlink(node(index));  
}  

private boolean isElementIndex(int index) {  
    return index >= 0 && index < size;  
}  

private boolean isPositionIndex(int index) {  
    return index >= 0 && index <= size;  
}  

private String outOfBoundsMsg(int index) {  
    return "Index: "+index+", Size: "+size;  
}  

private void checkElementIndex(int index) {  
    if (!isElementIndex(index))  
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
}  

private void checkPositionIndex(int index) {  
    if (!isPositionIndex(index))  
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
}  

/* 
 * 返回指定位置的节点 
 */  
Node<E> node(int index) {//返回第index个节点  
    // assert isElementIndex(index);  
    //判断在前半部分还是后半部分  
    if (index < (size >> 1)) {//index在前半部分  
        Node<E> x = first;  
        for (int i = 0; i < index; i++)//从前向后顺序查找  
            x = x.next;  
        return x;  
    } else {//index在后半部分  
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)//从后向前顺序查找  
            x = x.prev;  
        return x;  
    }  
}

• 与Deque接口一样，对指定位置元素的操作，内部还是会调用第二节的内部操作，不同的是，这里封装的是对元素操作，而第二节的方法是对底层链表的节点操作，两者是不一样的。

• 所以部分方法中基本都会先调用checkElementIndex(index);方法来确认index参数是否合法，如果不合法就直接抛出异常。

• 如果index参数合法，就会调用最下面的node(index)方法，即在链表中找到指定位置的节点，查找的方法采用顺序查找，先判断index是在前半部分还是后半部分，然后决定是从前向后查找还是从后向前查找。

  ​

2、Search Operations

查找操作，有两个方法查找某个元素第一次出现的位置，一个是从前向后查找，一个是从后向前查找。

// Search Operations  
 
   public int indexOf(Object o) {//返回某个元素第一次出现的位置，如果没有则返回-1  
       int index = 0;//考虑元素是否为null两种情况  
       if (o == null) {//  
           for (Node<E> x = first; x != null; x = x.next) {//从前向后遍历  x.item == null  
               if (x.item == null)//  
                   return index;//  
               index++;//  
           }  
       } else {//  
           for (Node<E> x = first; x != null; x = x.next) {//    o.equals(x.item)  
               if (o.equals(x.item))//  
                   return index;//  
               index++;//  
           }  
       }  
       return -1;  
   }  
 
   public int lastIndexOf(Object o) {//返回从后向前第一次出现的位置，原理同上，只是顺序不同  
       int index = size;  
       if (o == null) {  
           for (Node<E> x = last; x != null; x = x.prev) {  
               index--;  
               if (x.item == null)  
                   return index;  
           }  
       } else {  
           for (Node<E> x = last; x != null; x = x.prev) {  
               index--;  
               if (o.equals(x.item))  
                   return index;  
           }  
       }  
       return -1;  
   }

有一点需要注意的就是List中允许出现null，所以在判断元素相等的时候，需要判断该元素是否为null，如果是是null则用==判断，否则使用equals判断相等。

3、toArray

使用方法与ArrayList中一样。一个是返回Object数组，还有一个是返回指定类型的数组。

public Object[] toArray() {  
    Object[] result = new Object[size];  
    int i = 0;  
    for (Node<E> x = first; x != null; x = x.next)  
        result[i++] = x.item;  
    return result;  
}  

@SuppressWarnings("unchecked")  
public <T> T[] toArray(T[] a) {  
    if (a.length < size)  
        a = (T[])java.lang.reflect.Array.newInstance(  
                            a.getClass().getComponentType(), size);  
    int i = 0;  
    Object[] result = a;  
    for (Node<E> x = first; x != null; x = x.next)  
        result[i++] = x.item;  

    if (a.length > size)  
        a[size] = null;  

    return a;  
}

4、其他

public boolean contains(Object o) {  
    return indexOf(o) != -1;  
}  

public int size() {  
    return size;  
}  

public boolean add(E e) {  
    linkLast(e);  
    return true;  
}  

public boolean remove(Object o) {//删除指定元素，同样要考虑是否为null两种情况  
    if (o == null) {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}  

public boolean addAll(Collection<? extends E> c) {  
    return addAll(size, c);  
}  

public boolean addAll(int index, Collection<? extends E> c) {//将集合中所有元素加入链表的指定位置  
    checkPositionIndex(index);//检查插入的位置是否合法  

    Object[] a = c.toArray();//将集合中元素转换为Object数组  
    int numNew = a.length;//numNew即集合中元素的个数  
    if (numNew == 0)//  
        return false;//  

    Node<E> pred, succ;//定义两个节点保存前驱与后继节点，考虑是否在末尾插入两种情况  
    if (index == size) {//如果在末尾插入  
        succ = null;//不用指定后继节点  
        pred = last;//前驱节点为尾节点  
    } else {//如果不在末尾插入，则需要通过index找到要插入的那个节点  
        succ = node(index);//后继为找到的那个节点  
        pred = succ.prev;//前驱为找到那个几点的前驱  
    }  

    for (Object o : a) {//for each循环遍历a数组，逐个插入  
        @SuppressWarnings("unchecked") E e = (E) o;//强制转型为指定类型  
        Node<E> newNode = new Node<>(pred, e, null);//新建一个节点，数据域为转型后的数组元素，指定前驱  
        if (pred == null)//如果前驱为null  
            first = newNode;//说明在头节点前插入，那么新节点为新的头节点  
        else//如果不为null，说明前面有节点  
            pred.next = newNode;//将前面节点的后继指向新节点  
        pred = newNode;//更新前驱节点  
    }  
    //所有节点插入完毕后更新尾节点  
    if (succ == null) {//如果后继节点为null，说名在末尾插入  
        last = pred;//那么刚才最后一个前驱就是尾节点  
    } else {//如果不在末尾插入，后面还有元素  
        pred.next = succ;//连接前驱与后继节点  
        succ.prev = pred;//  
    }  

    size += numNew;//更新元素个数  
    modCount++;  
    return true;  
}    

public void clear() {//清除所有元素  
    // Clearing all of the links between nodes is "unnecessary", but:  
    // - helps a generational GC if the discarded nodes inhabit  
    //   more than one generation  
    // - is sure to free memory even if there is a reachable Iterator  
    for (Node<E> x = first; x != null; ) {  
        Node<E> next = x.next;  
        x.item = null;  
        x.next = null;  
        x.prev = null;  
        x = next;  
    }  
    first = last = null;  
    size = 0;  
    modCount++;  
}