从源码出发，谈谈ArrayList、LinkedList

前言

android 开发适配器里面存放数据用的最多的就是ArrayList，大家有看过ArrayList源码吗，ArrayList的优点和确定是什么，有没有什么数据结构可以替换ArrayList呢？本篇文章带领大家从源码角度出发一起看看ArrayList和LinkedList。

1. ArrayList

ArrayList本质是数组。它里面的元素都保存在elementdata[] 这样一个数组里面

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!! 给ArrayList扩容
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add的核心代码是System.arraycopy(elementData, index, elementData, index + 1, size - index);

private static void arraycopy(char[] src, int srcPos, char[] dst, int dstPos, int length) {
    if (src == null) {
        throw new NullPointerException("src == null");
    }
    if (dst == null) {
        throw new NullPointerException("dst == null");
    }
    if (srcPos < 0 || dstPos < 0 || length < 0 ||
        srcPos > src.length - length || dstPos > dst.length - length) {
        throw new ArrayIndexOutOfBoundsException(
            "src.length=" + src.length + " srcPos=" + srcPos +
            " dst.length=" + dst.length + " dstPos=" + dstPos + " length=" + length);
    }
    if (length <= ARRAYCOPY_SHORT_CHAR_ARRAY_THRESHOLD) {
        // Copy char by char for shorter arrays.
        if (src == dst && srcPos < dstPos && dstPos < srcPos + length) {
            // Copy backward (to avoid overwriting elements before
            // they are copied in case of an overlap on the same
            // array.)
            for (int i = length - 1; i >= 0; --i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        } else {
            // Copy forward.
            for (int i = 0; i < length; ++i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        }
    } else {
        // Call the native version for longer arrays.
        arraycopyCharUnchecked(src, srcPos, dst, dstPos, length);
    }
}

为了方便大家了解，我画了一个图

image

所以copy的操作元素就是遍历元素，然后进行替换操作。
同理，remove()方法也是用了System.copy()方法，只不过是把元素往前挪位置了

掌握了ArrayList方法的原理后我们不难发现，如果我们要往ArrayList中添加元素的时候，如果是往最后一个位置添加元素的时候速度是最快的，往中间添加元素，因为涉及到元素位移操作，所以效率相对较低。由于arraylist本质是数组，数组在内存中是连续的空间，所以get(index)是很快的，直接通过elementdata[index]这个数组就能拿到。

从时间复杂度来说，ArrayList插入和删除的时候时间复杂度为O(n)，获取元素的时间复杂度为O(1)。

那么有没有插入和删除相对较快的数据结构呢。

2. LinkedList

LinkedList是一个双链表。

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        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)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

就是把之前的链断开，前面的元素的尾结点指向新添加的元素，新添加的元素的头结点指向前一个元素。后一个元素的头结点指向当前元素，当前元素的尾结点指向后一个元素。

同样的画个图方便大家了解
<meta charset="utf-8">

2.png

接下来看下get()方法

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

...

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

get()方法最终用for()循环是轮询获取元素，所以效率较低。

从时间复杂度来说，LinkedList插入和删除的时候时间复杂度为O(1)，获取元素的时间复杂度为O(n)。

有没有一种数据结构能够结合以上两个的优点呢，下篇文章咱们一起学习下HashMap的原理。