LinkedList源码分析-JDK1.7

浅析JDK1.7 LinkedList源码。

写在开篇

简单介绍一下LinkedList，它使用了双向循环链表作为其存储的数据结构。由于链表的特点是可以自由的添加新的元素，因此LinkedList不需要初始化大小，且列表伸缩性比ArrayList强(ArrayList只能伸展，不能收缩)。LinkedList在根据一个index查找随机节点时，会判断此index在左半区还是右半区，这样就可以选择是从头节点正向遍历，还是从尾节点反向遍历，要比只从头节点遍历的效率高一些。

类的继承结构

ArrayList继承AbstractSequentialList抽象类，实现了List（规定了List的操作规范）、Deque（双端队列）、Cloneable（可拷贝）、Serializable（可序列化）这几个接口。

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

存储结点–Node

private static class Node<E> {
       E item;	//结点数据元素
       Node<E> next;	//后置结点
       Node<E> prev;	//前置结点
       // ...
   }

成员变量

/**
 * 元素个数
 */
transient int size = 0;

/**
 * 链表的头结点
 */
transient Node<E> first;

/**
 * 链表的尾结点
 */
transient Node<E> last;

构造方法

LinkedList有两个构造方法。

/**
    * 空构造方法
    */
   public LinkedList() {
   }

   /**
    * 以实现了Collection接口的集合类，来初始化链表
    */
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

List接口的实现

add()

LinkedList有两个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));
   }

接下来详细看看add()方法的核心：

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) {
    final Node<E> pred = succ.prev; // 保存succ的前置结点
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;	// 将succ的前置结点改为新结点
    if (pred == null)
    	// 如果succ的前置结点为空，则设置新结点为头结点
        first = newNode;
    else
    	// 如果不为空，设置新结点前置结点为刚刚保存的pred
        pred.next = newNode;
    size++;
    modCount++;
}

put()

put()比较简单，直接贴源码。

public E set(int index, E element) {
       checkElementIndex(index); 
       Node<E> x = node(index);
       E oldVal = x.item;
       x.item = element; 
       return oldVal;
   }

get()

public E get(int index) {
       checkElementIndex(index);
       return node(index).item;
   }
   
   Node<E> node(int index) {
   	// 判断下标在前半段还是后半段，决定从头结点还是尾结点开始遍历
       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;
       }
   }

remove()

public boolean remove(Object o) {
       if (o == null) { // 删除元素值为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;
   }
   
   E unlink(Node<E> x) {
       final E element = x.item;
       final Node<E> next = x.next;
       final Node<E> prev = x.prev;

	// prev为空，则next为头结点
       if (prev == null) {
           first = next;
       } else {
           prev.next = next;
           x.prev = null;
       }

	// next为空，则prev为尾结点
       if (next == null) {
           last = prev;
       } else {
           next.prev = prev;
           x.next = null;
       }

       x.item = null;
       size--;
       modCount++;
       return element;
   }