Java中ArrayList和LinkedList的区别

热衷学习，热衷生活！😄

沉淀、分享、成长，让自己和他人都能有所收获！😄

两者数据结构不同，ArrayList是基于数组实现、LinkedList是基于双向链表实现。从获取、删除、插入、内存开销这几个点来说明两者的区别。

1、获取：

ArrayList的获取比LinkedList获取相比非常快，因为ArrayList的get方法的时间复杂度为O(1)，而LinkList的为O(n)。

ArrayList的get方法源码：

public E get(int index) {
    rangeCheck(index);
    
    return elementData(index);
}
E elementData(int index) {
    // 直接下标获取数组值, 时间复杂度为O(1)
    return (E) elementData[index];
}

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

LinkList还提供获取首位元素的方法，getFirst、getList，这两个方法的时间复杂度为O(1)。

结论：ArrayList元素的获取性能比LinkedList高。

2、删除：

LinkedList删除时间复杂度为O(1)，这个O(1)只是从删除的操作来说，因为LinkedList在删除的时候也会进行for循环获取删除的节点。而ArrayList删除时间复杂度是可变的，删除第一个元素是最坏的情况时间复杂度为O(n)，这是因为删除第一个元素要进行数组的copy从而移动数组，删除最后一个元素是最好的情况时间复杂度为O(1)，这是因为ArrayList删除最后一个元素时就是把最后一个元素置为null。

LinkedList删除方法源码如下：

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

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x){
    final E emelemt = 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还提供了删除收尾元素的方法，removeFirst()、removeLast()。

ArrayList删除源码如下：

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

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; // clear to let GC do its work

     return oldValue;
 }

结论：LinkedList元素删除比ArrayList要快。

原因：LinkedList的每个元素都维护着两个指针，它们指向列表中的两个相邻元素。因此删除只需要更改将要删除的节点的两个相邻节点中的指针位置。而ArrayList都要进行数组copy移动填充删除元素创建的空间。

3、插入

LinkedList add方法就是向尾部插入方法，时间复杂度为O(1)，而ArrayList add方法时间复杂度是可变的最坏为O(n)，原因是ArrayList扩容的时候需要元素的复制移动。

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

ArrayList add方法扩容源码如下：

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