源码级别说明ArrayList和LinkedList的区别

首先二者都是实现了List接口的不同实现,并且都不是线程安全的

区别一 : 数据结构方面

ArrayList底层使用的是动态数组来存储元素,初始化大小DEFAULT_CAPACITY = 10;
LinkedList底层使用的是双向链表来存储元素

区别二 : 使用场景

ArrayList更适用于随即查找
LinkedList更适合删除和添加
再因为LinkedList在实现了List接口的基础上还实现了Deque接口,所以LinkedList还被用来做双端队列

区别三 : get方法

ArrayList的get方法

ArrayList arrayList = new ArrayList();
arrayList.get(1);

LinkedList的get方法

LinkedList linkedList = new LinkedList();
linkedList.get(1);

看起来和ArrayList的get方法一样都是使用下标直接获取,但是因为LinkedList底层使用的是双向链表来存储元素,所以他需要先进行遍历,才能找到对应下标,源码如下

//测试代码
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
->断点 System.out.println(linkedList.get(1));
//LinkedListt的get方法
public E get(int index) {
    //检查LinkedList中是否有该下标,没有的话就抛IndexOutOfBoundsException异常
    checkElementIndex(index);
    return node(index).item;
}
//node(index).item;
Node<E> node(int index) {
    // assert isElementIndex(index);保证index是存在的
    //size右移一位,就是size/2
    //判断index和size/2的原因是
    //index<size>>1,就从前往后遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } 
    //index>size>>1,就从后往前遍历
    else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList是有两个查询方法是不需要遍历的,直接定位到就可以获取

linkedList.getFirst();
linkedList.getLast();

原因如源码所示

//LinkedList自身的属性有first和last,一直持续的记录first和last这两个属性
//所以不需要遍历就可以直接定位到
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
transient Node<E> first;
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
transient Node<E> last;

区别四 : 添加操作

ArrayList的添加操作

1 . arrayList.add(element),直接添加到数组的最后一个位置

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //直接添加到数组的最后一个位置
    elementData[size++] = e;
    return true;
}

2 . arrayList.add(index,element),添加指定位置

public void add(int index, E element) {
    //检查这个index,如果index > size || index < 0
    //throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //数组移动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

LinkedList的添加操作

1 . LinkedList.add(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)
        //如果last为空,就直接为头节点
        first = newNode;
    else
        //不为空,就插入到最后
        l.next = newNode;
    size++;
    modCount++;
}

2 . LinkedList.add(index,element),添加指定位置

public void add(int index, E element) {
    //检查这个index,如果index > size || index < 0
    //throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    checkPositionIndex(index);
    //如果index就是Linked的大小,那么就说明是插入到最后一个节点,就直接调用linkLast方法
    if (index == size)
        linkLast(element);
    else
        //如果不是size,那么就说明需要插入到last节点的前面的节点,就调用linkBefore方法
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //取通过下标确定出的节点的前驱节点
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        //如果pred为空,那么就说明pred就是头节点,那就直接为头节点
        first = newNode;
    else
        //如果pred不为空,就直接直接插入到next
        pred.next = newNode;
    size++;
    modCount++;
}

区别五 : 扩容操作

LinkedList是不存在扩容的,主要是ArrayList的扩容操作

ArrayList的扩容

例 :

//初始化大小为2
ArrayList arrayList = new ArrayList(2);
arrayList.add(1);
arrayList.add(2);
//尝试去插入第三个元素
System.out.println(arrayList.add(3));

插入方法

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

ensureCapacityInternal()方法,就是确保可以放的下这个元素,就是检查是否需要扩容

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断最小容量减去数组长度是否大于0,大于就说明需要扩容
    if (minCapacity - elementData.length > 0)
        //扩容方法
        grow(minCapacity);
}

grow(minCapacity)方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //新长度为旧长度+旧长度/2
    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;
}

区别六 : 删除操作

ArrayList的删除

public E remove(int index) {
    //检查这个index是否正确
    rangeCheck(index);
    modCount++;
    //取出index的值
    E oldValue = elementData(index);
	//判断要删除的那个元素是否是否是唯一的那个元素
    int numMoved = size - index - 1;
    //不是就删除,并且复制移动数组
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //是的话,就将数组置为空,等待GC
    elementData[--size] = null; // clear to let GC do its work
	//返回删除的值
    return oldValue;
}

LinkedList的删除

//其实就是普通的链表删除操作,断开连接
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;
}

总结

如上所述,即为ArrayList和LinkedList的源码层面的区别分析,那么到底在实际开发中具体使用什么呢?

ArrayList比较适合随机查找的原因是因为底层是数组,可以直接通过index确定到具体的element,时间复杂度为0(1)
ArrayList的增删改比较耗时原因是不仅是因为需要扩容,而且还有System.arraycopy()和Arrays.copyOf()这两个方法的存在,就是在对数组进行改动的时候,需要将数组进行复制移动,时间复杂度为0(n)
LinkedList比较适合增删改的原因就是只是单纯的链表增删改,时间复杂度为0(1),如果是指定下标增删改的话就是0(n),因为需要遍历嘛
LindedList查找比较耗时就是因为需要遍历链表,其实他底层还使用了二分法进行遍历优化,但是还是比较慢,时间复杂度为O(n),但是如果是查第一个或者最后一个,因为有getFirst()和getLast()这两个方法t的存在,时间复杂度为0(1)

补充知识

我们会在ArrayList和LinkedList的源码中看到很多的modCount++,这是什么呢?

modCount字面意思就是modify count 修改次数

那为什么要记录修改次数的呢?

我们知道ArrayList和LinkedList不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了list，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。

注意!!!,在JDK5和JDK6的时候，也许是正确的，因为在JDK5和JDK6中变量modCount确实声明为volatile。但在JDK7和JDK8中，已经没有这样声明了！！！！！

JDK7和JDK8中,说的是此异常并不总是表示对象已被其他线程同时修改。如果单个线程发出一系列违反对象约定的方法调用，则该对象可能会抛出此异常。例如，如果线程使用有fail-fast机制的迭代器在集合上迭代时修改了集合，迭代器将抛出此异常。,就是说ConcurrentModificationException这个异常不一定是因为迭代器在集合上迭代时修改了集合,还有可能是因为违反对象约定的方法调用等等