从源码了解ArrayList和LinkedList

面试题：ArrayList和LinkedList的区别？

ArrayList和LinkedList是List的两种基本实现，ArrayList是List的数组实现，LinkedList是List的双向链式实现。ArrayList可以指定位置访问，在查询、修改时效率比LinkedList高，添加、删除时需要后面的所有元素都移动，效率比LinkedList低。LinkedList不能指定位置访问，查询、修改时需要遍历节点，效率比ArrayList低，添加、删除时不需要移动元素，只需要修改对应指针，效率比ArrayList高。两者都是线程不安全的。

源码分析：

1.ArrayList

(1)类定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Arraylist实现了RandomAccess（支持快速访问接口），Cloneable（复制接口），Serializable（序列化接口）。

其主要继承和实现关系如下

ArrayList-->AbstractList-->AbstractCollection-->Collection-->Iterable

ArrayList-->List-->Collection-->Iterable

上面那条线主要是优化get，set，add等基础方法的内部实现，下面这条线是List的基本线。

（2）主要变量

transient Object[] elementData;

private int size;

ArrayList主要的数据结构是Object数组，通过size记录其当前已有值的容量，size并非当前最大容量，当前最大容量是elementData.lenth，一些基本方法是通过直接调用数组的基本方法。

(3)主要构造方法

无参构造方法

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final int DEFAULT_CAPACITY = 10;

有参构造方法

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

private static final Object[] EMPTY_ELEMENTDATA = {};

无参构造方法的默认值大小是10，有参构造方法的参数为大于等于0的整数，如果参数为0，则默认一个空的Object数组，如果参数大于0，则为一个大小为指定大小的Object数组，构造方法构造的数组都未初始化，所以里面的值都为null。

（4）主要方法

查询

public E get(int index) {

    rangeCheck(index);
    return elementData(index);

}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

修改

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

删除

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    elementData[--size] = null;
    return oldValue;
}

 

添加

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, 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;
   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);
}

ArrayList查询时直接调用数组的基本方法。

ArrayList修改时直接调用数组的基本方法并设置值。

ArrayList删除时，先删除元素，然后调用System.arraycopy的native方法将该元素后面的元素前移一位。

ArrayList新增元素时会检测容量是否足够，如果容量不够，会进行扩容操作，扩容计算公式为oldCapacity + (oldCapacity >> 1),也就是原来大小的1.5倍，扩容的方式是调用Array.copyOf方法，其底层调用的是System.arraycopy的native方法，是复制了原来的值到一个新的object数组中。如果是指定位置新增还需将新增元素后的所有元素向后移一位。

从上面可见，ArrayList查询和修改时操作少、效率比较高，删除和新增时操作多、效率比较低。

（5）线程安全问题

从上面add方法源码分析，ArrayList执行add方法时有两个地方导致其可能出现线程不安全：

第一点：ensureCapacityInternal方法在多个线程中可能会都判断成未超过容量，都会进行+1操作，如果在临界值范围时有可能出现数组越界，

第二点：size++并非原子操作，在多个线程中可能会出现一个线程覆盖另外一个线程的值。

（6）CopyOnWriteArrayList

 CopyOnWriteArrayList主要继承和实现关系上只实现是List接口，次要继承和实现关系和ArrayList一致

final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;

底层基本实现也是用的object数组，加上了volatile 关键字和ReentrantLock 重入锁。在set，add，remove，iterator等写相关的方法中，全程加锁，所以是线程安全的。

2.LinkedList

（1）类定义

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

LinkedList实现了Cloneable（复制接口），Serializable（序列化接口）。

其主要继承和实现关系如下

LinkedList-->AbstractSequentialList-->AbstractList-->AbstractCollection-->Collection-->Iterable

LinkedList-->List-->Collection-->Iterable

LinkedList-->Deque-->Queue-->Collection-->Iterable

从继承关系上看出，前两条线和ArrayList是基本一致的，后面这条线是队列线，且这是个双端队列。

（2）主要变量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

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

LinkedList主要存储结构是以节点的形式，内部定义了个静态的节点类，拥有向前和向后的指针，内部存储的是指定泛型。

（3）主要构造方法

public LinkedList() {
}

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

LinkedList主要构造方法除了默认值外，未设置其他任何值。

（4）主要方法

查询

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

修改

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

 

删除

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

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

添加

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
       l.next = newNode;
   size++;
   modCount++;
}

LinkedList查询时，判断该元素属于前半段或者是后半段，前半段从头节点开始往后遍历到指定位置，如果是后半段从尾节点往前遍历到指定位置。

LinkedList修改时，需要先查询到指定节点，直接修改元素。

LinkedList删除时，需要先查询到指定节点，删除元素，并将相应的指针位置改变，手动设置未null，方便GC。

LinkedList增加时，直接在尾结点后面新增，并将相应的指针位置改变，如果是指定位置新增，需要先查询到指定节点。

linkedList除去直接增加不需要查询，其他操作都需要查询操作，而查询效率并不是很高，最差需要size/2的遍历。

（5）线程安全性

LinkedList指针操作并非线程安全，ConcurrentLinkedQueue是线程安全版本。