Java-List 集合介绍- ArrayList和 LinkedList 区别

List 集合介绍

List 集合是有序的，可以重复。可对其中每个元素的插入位置进行精确地控制，可以通过索引来访问元素，遍历元素。在 List 集合中，我们常用到 ArrayList 和 LinkedList 这两个类。

ArrayList 集合介绍

ArrayList 底层通过数组实现，随着元素的增加而动态扩容。查询快，增加和删除慢，线程不安全。

ArrayList 属性主要由数组长度 size、对象数组 elementData、初始化容量 default_capacity 等组成， 其中初始化容量默认大小为 10。

查询快

ArrayList 是基于数组实现的，获取元素的时候是非常快，底层源码如下:

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

增加和删除慢

ArrayList 新增元素的方法有两种，一种是直接将元素加到数组的末尾，另外一种是添加元素到任意位置。底层源码如下：

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

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

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

添加元素之前，都会先确认容量大小，如果容量够大，就不用进行扩容；如果容量不够大，就会按照原来数组的 1.5 倍大小进行扩容，在扩容之后需要将数组复制到新分配的内存地址。

ArrayList 在每一次有效的删除元素操作之后，都要进行数组的重组，并且删除的元素位置越靠前，数组重组的开销就越大。底层源码如下：

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

线程不安全

ArrayList 的线程不安全体现在多线程调用 add 方法的时候。

• 当在需要进行数组扩容的临界点时，如果有两个线程同时来进行插入，可能会导致数组下标越界异常。
• 由于往数组中添加元素不是原子操作，所以可能会导致元素覆盖的情况发生。

LinkedList 集合介绍

LinkedList 底层通过双向链表来实现，随着元素的增加不断向链表的后端增加节点。查询慢，增加和删除快，线程不安全。

LinkedList 属性主要包含链表的链头 first 、链表的链尾 last 、双向链表中节点个数 size

查询慢

我们首先要通过循环找到要查询的元素，如果要查询的位置处于 List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。在 for 循环遍历的情况下，每一次循环都会去遍历半个 List。

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

增加和删除快

LinkedList 新增元素的方法有两种，一种是将添加的元素加到队尾，首先是将 last 元素置换到临时变量中，生成一个新的 Node 节点对象，然后将 last 引用指向新节点对象，之前的 last 对象的前指针指向新节点对象。另外一种是添加元素到任意位置，如果我们是将元素添加到任意两个元素的中间位置，添加元素操作只会改变前后元素的前后指针，指针将会指向添加的新元素。底层源码如下：

public boolean add(E e) {
    linkLast(e);
    return true;
}


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

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

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

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

LinkedList 删除元素的操作中，我们首先要通过循环找到要删除的元素，如果要删除的位置处于 List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。

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

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

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

线程不安全

LinkedList 的线程不安全体现在多个线程同步访问的时候可能会导致数据损坏。