上学时学过ArrayList底层采用数组实现，LinkedList底层基于链表实现。ArrayList读取效率高，LinkedList增删改效率高。

下面我们看看具体的实现：

ArrayList

ArrayList中有个Object的elementData数组用来承载数据，transient标识该字段不需要被序列化。

/** * 空ArrayList的elementData会赋值成一个空的Object数组{} * 当添加第一个元素的时候该数组会扩容默认的容量10 */transient Object[] elementData; // non-private to simplify nested class access

添加对象时：

public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}private void ensureCapacityInternal(int minCapacity) {	// 空数组时，默认容量为10    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // 如果容量不足时    if (minCapacity - elementData.length > 0)        grow(minCapacity);}/** * 数组的最大值，超过之后将会抛出OutOfMemoryError */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    // 每次扩容为数组的原长度的一半，故优化时可先初始化数组的长度可提高效率和降低内存占用    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    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);}private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow        throw new OutOfMemoryError();    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

remove对象

/** * 每次remove的时候都会去遍历一遍elementData */public boolean remove(Object o) {    if (o == null) {        for (int index = 0; index < size; index++)            if (elementData[index] == null) {                fastRemove(index);                return true;            }    } else {        for (int index = 0; index < size; index++)            if (o.equals(elementData[index])) {                fastRemove(index);                return true;            }    }    return false;}private void fastRemove(int index) {    modCount++;    int numMoved = size - index - 1;    if (numMoved > 0)        // 将elementData的尾部copy到elementData中        System.arraycopy(elementData, index+1, elementData, index,                         numMoved);    elementData[--size] = null; // clear to let GC do its work}

System中的arraycopy

/** * native关键字说明其修饰的方法是一个原生方法 * @param      src      源数组。 * @param      srcPos   源数组起始位置 * @param      dest     目标数组 * @param      destPos  目标数据起始位置 * @param      length   复制的数量 */public static native void arraycopy(Object src,  int  srcPos,                                        Object dest, int destPos,                                        int length);

LinkedList

LinkedList没有初始容量一说，他的数据结构如下:

/** * Pointer to first node. * Invariant: (first == null && last == null) || *            (first.prev == null && first.item != null) */transient Node
    
      first;/** * Pointer to last node. * Invariant: (first == null && last == null) || *            (last.next == null && last.item != null) */transient Node
     
       last;
     
    

node的结构如下：

private static class Node
    
      {    E item;    Node
     
       next;    Node
      
        prev;    Node(Node
       
         prev, E element, Node
        
          next) {        this.item = element;        this.next = next;        this.prev = prev;    }}
        
       
      
     
    

linkFirst、linkLast

/** * Links e as first element. */private void linkFirst(E e) {    final Node
    
      f = first;    final Node
     
       newNode = new Node<>(null, e, f);    first = newNode;    if (f == null)        last = newNode;    else        f.prev = newNode;    size++;    modCount++;}/** * Links e as last element. */void linkLast(E e) {    final Node
      
        l = last;    final Node
       
         newNode = new Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}
       
      
     
    

注意:在LinkedList存储第一个Node节点的时候，first和last同时指向该node，然后分别向2端扩展。

HashSet

private transient HashMap
    
      map;
    

HashSet中采用一个HashMap来承载数据，由于大家对HashMap都比较熟悉，这里不多说。