收录面试高频题汇总，面试复习 or 查漏补缺

本文讲解Java中的List数据结构以及其常见方法的源码

什么是ArrayList

什么是LinkedList

什么是Vector

List

链表，是最常用的数据结构之一，具有有序、可重复的特点。

ArrayList

ArrayList底层结构使用的是Object数组

transient Object[] elementData;

数组的特点就是一块连续的内存空间，用index访问元素，适合随机访问，复杂度O(1)，但是对数组中间的元素进行插入和删除时比较困难，需要对数组进行大量copy操作。

数组

ArrayList常见的方法

• add

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

• remove

public E remove(int index) {
    rangeCheck(index); // 检查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;
}

• grow

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)  
        newCapacity = minCapacity;    // 新容量小于最小需要的容量，新容量直接等于最小需要的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) 
        newCapacity = hugeCapacity(minCapacity);   // 大于数组的最大容量，抛出oom或等于最大数组容量
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

一般初始容量为0，第一次分配容量为10个，后续扩容为newCapacity = oldCapacity + (oldCapacity >> 1);,即原大小的1.5倍

LinkedList

LinkedList底层结构是通过构造Node节点，且节点之间通过指针的方式连接起来形成链表的

private static class Node<E> {
    E item;  // 链表节点存储的数据
    Node<E> next; // 指向下一个节点
    Node<E> prev; // 指向前一个节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

链表的特点

• 适合频繁的插入和删除操作，只需要改变节点的指针即可
• 查询复杂度随着集合大小增加而提升，查询链表某个元素时，需要遍历操作

链表

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);  // 构造新node节点
    last = newNode;   // 更新当前最新的节点
    if (l == null)
        first = newNode;  // 没有最新节点，第一个节点记为当前最新节点
    else
        l.next = newNode; // 存在最新节点，最新节点的下个节点就是当前要增加的节点
    size++;
    modCount++;  // 修改计数
}

• remove

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index)); // 拿到index对应的节点，然后释放节点
}
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;
}

• get(index)；采用对半查找

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

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 以size/2为中点，判断index做小于中点还是大于中点
    if (index < (size >> 1)) { // index小于size/2，那么从头开始遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {  // index大于size/2，那么从尾部开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Vector

Vector底层结构使用的是Object数组

protected Object[] elementData;

Vector与ArrayList比较相似，Vector是比较老的一个集合，是线程安全的，实现线程安全的方式比较简单，通过在对数组进行修改的方法上加上synchronized，常见的有addElement、removeElement等

Vector常见方法

• addElement

public synchronized void addElement(E obj) { // 方法使用了同步锁
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

• removeElement

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

CopyOnWriteArrayList

CopyOnWriteArrayList底层使用的数据结构是Object数组

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

CopyOnWriteArrayList是一个线程安全的List集合，使用到的技术是CopyOnWrite，简称COW。

CopyOnWrite

什么是CopyOnWrite？中文翻译为写入时复制，就是在对数据写入或修改时，拷贝一份与原来一样的数据，在拷贝的数据上进行写入或修改，这样原来数据依旧可以读访问，当拷贝的数据写入或修改完成后，将拷贝的数据替换原来的数据，后续的读访问就可以读到最新的数据了。

接下来，看CopyOnWriteArrayList是怎么实现的，如下图，它通过使用Java中的ReentrantLock和volatile保证读写分离，从而在并发读写时实现线程安全，适合读多写少的场景。

copyOnWrite

CopyOnWriteArrayList常见方法

• add

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 写数据，同步锁lock，控制并发
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); // 拷贝新数组
        newElements[len] = e; // 赋值
        setArray(newElements); // 替换原来数组
        return true;
    } finally {
        lock.unlock(); // 释放同步锁
    }
}

• remove

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 写数据，同步锁lock，控制并发
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else { // 除了index的数据，其他拷贝到到新数组，
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index); 
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 替换原来数组
        }
        return oldValue;
    } finally {
        lock.unlock(); // 释放同步锁
    }
}

常见List集合的区别

常见非线程安全集合使用ArrayList或LinkedList，线程安全优先考虑CopyOnWriteArrayList。

结尾

本文收录至我的《面试高频题及答案汇总》系列。

你努力走过的路，每一步都算数。