ArrayList和LinkedList

1 ArrayList和LinkedList简介

ArrayList底层是数组，查询快、增删慢；LinkedList底层是链表，查询慢、增删快；

ArrayList底层是数组，存储空间是连续的，可以根据寻址方式直接找到对应的元素位置，时间复杂度是O(1)。

举例来说：在一条街上，第一家店是001号，那么005号在第五间：

但LinkedList底层是链表，存储空间不连续，需要通过指针关联，在查询过程中需要不断跳转新的地址：

这也是ArrayList比LinkedList查询快的原因。

Java中的原生的数组是不能扩容的，如果初始化时申请了5个元素空间，那么就最多能存5个元素。ArrayList底层也是数组，但是支持动态扩容，所以ArrayList是动态数组：

假设原始容量为5，那么插入新元素时就会扩容，元素拷贝等耗时操作，这就是ArrayList增删慢的原因。但是ArrayList增删元素必然会惩罚扩容和拷贝吗？

插入同理，尾部插入时不涉及元素拷贝。

LinkedList中，理想状态下，链表的增删操作时间复杂度为O(1):

2 问题 2.1 ArrayList如何添加元素？

扩容：往ArryList中添加元素的时候，会首先检查是否需要扩容。当size == elementData.length时，表示数据数量已经超过了数组容量，需要扩容，扩容后的数组的长度为原来数组长度的1.5倍；
复制：当扩容检查完毕后，如果添加的元素不在数组尾部，则将索引后面的元素通过System.arraycopy往后移动一位；
赋值：将值赋给数组中的对应索引，并将size++；

如果此时ArrayList的长度为size，在多线程运行的情况下，线程A想要将元素存放在索引为index的位置上，但此时CPU暂停线程A的调度，线程B得到运行的机会，也是向index的位置上添加元素。之后线程A和线程B都继续运行，都会增加size的值，这样数组的长度就变成了size + 2，这样就线程不安全了。

2.2 ArrayList是否能无限添加元素？会抛出异常吗？

可以无限添加，不会抛出异常。ArrayList会自动为其扩容，扩容后的大小是int newCapacity = (oldCapacity * 3) / 2 + 1。

2.3 ArrayList和LinkedList的时间复杂度？

ArrayList是线性表（数组）：

add(E e)：在数组尾部添加元素，时间复杂度为O(1)；
add(int index, E element)：在索引为index的位置添加元素，需要后面的元素后移，时间复杂度为O(n)；
remove(int index)/remove(Object o)：删除元素，需要后面的元素后移，时间复杂度为O(n)；
set(int index, E element)：修改元素，时间复杂度为O(1)；
get(int index)：获取索引为index的元素，时间复杂度为O(1)；

LinkedList是链表操作：

add(E e)：在数组尾部添加元素，时间复杂度为O(1)；
add(int index, E element)：在索引为index的位置添加元素，指针指向操作，时间复杂度为O(1)；
remove(int index)/remove(Object o)：删除元素，指针指向操作，时间复杂度为O(1)
set(int index, E element)：修改元素，时间复杂度为O(n)；
get(int index)：获取索引为index的元素，时间复杂度为O(n)；

2.4 ArrayList线程安全吗？为什么？如何解决多线程问题？

ArrayList线程不安全，因为相关的操作方法没有做同步，操作没有原子性，在多线程环境下会出现变量的读写异常。比如size++是非原子性的，如果两个线程同时执行，两个线程分别读了size的值，再分别执行size++，最后size的值变成了size + 1而不是size + 2。

多线程环境下使用CopyOnWriteArrayList保证线程安全，活着使用Collections.synchronizedList(list)，或者给多线程的操作加锁，或者使用Vector。

2.5 ArrayList与Vector区别？ArrayList效率高于Vector吗？

Vector是线程安全的ArrayList，Vector的方法使用synchronized修饰。

public class Vector extends AbstractList
  implements List, RandomAccess, Cloneable, java.io.Serializable {

  public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
  }
  public void add(int index, E element) {
    insertElementAt(element, index);
  }

  public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
      throw new ArrayIndexOutOfBoundsException(index
                                               + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
  }

  public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
      throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
                       numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
  }

  public boolean remove(Object o) {
    return removeElement(o);
  }

  public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
      removeElementAt(i);
      return true;
    }
    return false;
  }

  public synchronized E set(int index, E element) {
    if (index >= elementCount)
      throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
  }

  public synchronized E get(int index) {
    if (index >= elementCount)
      throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
  }

}

理论上来说，单线程下Vector的效率是低于ArrayList的，因为synchronized加锁必定会影响效率。然而在实际的情况，两者的效率相差无几，这是因为JVM对synchronized进行了优化。

参考

ArrayList和LinkedList区别？
【Java】ArrayList、LinkedList原理及相关面试题
ArrayList和LinkedList的⾯试题
【Java】ArrayList、LinkedList原理及相关面试题

ArrayList和LinkedList

Java相关栏目本月热门文章