ArrayList & LinkedList 源码

ArrayList 与 LinkedList

首先的强调下，这里的源码环境是JDK 1.8。

ArrayList

特点

• ArrayList 不是线程安全的;

相比于线程安全的Vector的源码来看，ArrayList没有使用synchronized关键字修饰其相关方法，也没有使用其他的让方法线程安全的操作。

• 底层数据结构是 数组

ArrayList的命名就是根据这个特性来的。

• 查找快，增删慢

ArrayList的底层数据结因为是通过数组方式来实现的，数据方式存储数据，需要在内存上按数组长度分配连续内存空间，内存空间地址就是 数组首元素的地址；

数组-查找快:

ArrayList 存储的是对象，对象的占用的内存大小是固定的 objSize，想获取ArrayList上指定 index 位置上的元素，可以直接获得对应 index 位置元素的存储地址，从而一次就能查找到该元素；

数组-增删慢:

如果每次增删都是在最后一个位置，就不存在这个特性了，但是实际引用中不可能只存在这种情况，更多的是中间的某个位置需要进行增删；

如果是中间某个index位置需要进行增删，这个index后面的所以元素都需要进行移位，这个移位操作就是拉胯性能的关键因素；

ArrayList源码

下面我们开始对照源码来查看其底层结构，我们不会关心所有的源码，而是选择从构造，增加元素，删除元素方法着手，查看其底层实现。

构造方法

查看构造方法之前，也将成员变量也一起看下；

   private static final int DEFAULT_CAPACITY = 10;
    // 默认是一个空数组   
    private static final Object[] EMPTY_ELEMENTDATA = {}; 
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正的存储数组
   transient Object[] elementData; // non-private to simplify nested class access
// 数组中元素的个数
   private int size;

//指定初始化 容器大小
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }
// 创建一个空的容器
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

这里只列出了2个构造方法，一个是参数，一个没参数，从两个构造方法，我们都可以确定，ArrayList 底层是通过数组的方式来存储数据的，就是这里的elementData；

为什么有两个空数组

• EMPTY_ELEMENTDATA

• DEFAULTCAPACITY_EMPTY_ELEMENTDATA

  从两个构造方法中可以看出，

  如果使用的无参构造方法，elementData 指向的就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的这个数组；

  如果使用的是有参构造方法，elementData 指向的就是
  EMPTY_ELEMENTDATA 的这个数组；

  这个两个数组是在JDK 1.7的时候优化的，这样我们使用new ArrayList（） 无参构造器创建的ArrayList统一指向同一个空数组；

add()方法

这里我们看两个add方法，一个是直接在数组尾部添加元素，一个是在数组中间位置添加元素；

数组尾部添加元素 add(E e)

先看代码

 public boolean add(E e) {
     // 确认容器大小
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
 }
 
private void ensureCapacityInternal(int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     }

     ensureExplicitCapacity(minCapacity);
 }   
 
 private void ensureExplicitCapacity(int minCapacity) {
     modCount++;

     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }
 
 private void grow(int minCapacity) {
     // overflow-conscious code
     // 原数数组中 元素个数
     int oldCapacity = elementData.length;
     // 按原数组中 元素个数的1.5倍（不完全是）确定新容器大小
     int newCapacity = oldCapacity + (oldCapacity >> 1);
     //  如果是空数组第一次添加元素 会执行这个 此时DEFAULT_CAPACITY = 10 
     if (newCapacity - minCapacity < 0)
         newCapacity = minCapacity;
      // 如果数组中的元素 达到了容器 阈值 Integer.Max - 8 ，就将容器大小设置为 Integer.Max
     if (newCapacity - MAX_ARRAY_SIZE > 0)
         newCapacity = hugeCapacity(minCapacity);
     // minCapacity is usually close to size, so this is a win:
     elementData = Arrays.copyOf(elementData, newCapacity);
 }

从源码中可以看到，ArrayList最大容量是 Integer.Max，如果超过了这个容量就不能再添加元素了。

在尾部添加元素，只需要保证数组容量够用，直接在数组尾部直接赋值。

数组中间位置添加元素 add(int index, E element)

下面来看下，在指定位置插入元素；

public void add(int index, E element) {
        //检查 index  的合法性
      rangeCheckForAdd(index);
// 确认容器大小 ，看是否要扩容
      ensureCapacityInternal(size + 1);  // Increments modCount!!
     // 关键代码： 移位操作  
      System.arraycopy(elementData, index, elementData, index + 1,
                       size - index);
     // 赋值                  
      elementData[index] = element;
     // 元素个数计数加1 
      size++;
  }
  

/**
 * src     原数组
 * srcPos  原数组偏移位置
 * dest    目标数组
 * destPos 目标数组偏移量
 * length  要copy的数据个数
 * / 
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

这里结合add(int index, E element) 来理解就是，将elementData数组，中index位置之后的length = size - index 个元素拷贝一份，都贴到目标数组dest （还是elementData）的destPos（index + 1）位置，也就是index后面的位置,如果感觉费劲，就直接看图理解吧。

remove（）方法

先看代码

  public E remove(int index) {
      //检查 index
      rangeCheck(index);
//操作次数计算加1
      modCount++;
      E oldValue = elementData(index);

      int numMoved = size - index - 1;
      // 如果不是最后一个元素： 将index 位置之后元素都向前移动一位
      if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
     // 将数组尾部的元素 赋值为null                      
      elementData[--size] = null; // clear to let GC do its work

      return oldValue;
  }

删除操作，就是将index位置之后的所以元素都向前移动一位，index + 1 位置的元素覆盖了原 index 位置的元素， 最后将数组尾部多出来的元素赋值为null;

LinkedList

特点

• LinkedList 不是线程安全的;

和ArrayList没有使用synchronized关键字修饰其相关方法，也没有使用其他的让方法线程安全的操作。

• 底层数据结构是 双链表

LinkedList的命名就是根据这个特性来的。从源码中可以看出 Node 对象是拥有 pre,next 变量，分别用于指向节点的前后两个节点；

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;
       }
   }

• 查找慢，增删快

链表-查找慢：

链表方式存储数据结构，在查询的时候，必须是通过某个节点（一把是fisrt节点或者last节点）依次遍历查找，所以查找速度相对比较慢。

链表-增删快:

在明确了要增删的节点的情况下，链表方式的存储结构只需要修改下上下节点的指针指向，就可以轻松做到对链表的增删；

图中描述的，在下面的源码解释中，我们就能了解到，事实上源码中就是如图所示那样操作的。

LinkedList源码

构造方法

   transient int size = 0;
// 保存头尾节点  方便查找 ，查找的时候判断下距离头部近，还是距离尾部近，在决定从头还是尾开始遍历
   transient Node<E> first;
   transient Node<E> last;

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

可以看到LinkedList，默认创建出来是一个空链。

add()方法

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

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
       // 如果不是第一个元素（空链的时候），将next指向最后一个元素
           l.next = newNode;
       size++;
       modCount++;
   }

在添加第一个元素的时候，会给first，last节点赋值。如果不是第一次添加元素，不仅会添加元素，还会将next 指向最后一个元素；

remove() 方法

public E remove(int index) {
    // 检查 index 
    checkElementIndex(index);
    return unlink(node(index));
}

//根据index 查找 节点元素node 
Node<E> node(int index) {
    // 如果 index  在前半段（index / 2）
    if (index < (size >> 1)) {
        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;
    }
}  
//  将 node 节点 移除链表
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

LinkedList 的移除元素:

• 1: 先根据index 和 size 确认 Node，通过判断是否是前半段，还是后半段来决定 从头遍历还是从尾巴开始遍历.
• 2: 找到要删除的Node , 根据Node 节点是双向链表的特征，可以直接将Node 节点的前一个元素的next 指向 Node 节点的 next元素。