当前位置 博文首页 > 氷泠：【2w字干货】ArrayList与LinkedList的区别以及JDK11中的底

最大化 缩小

    氷泠：【2w字干货】ArrayList与LinkedList的区别以及JDK11中的底

    作者：[db:作者] 时间：2021-09-12 12:10

    2021.09.08 更新

    1 概述

    本文主要讲述了ArrayList与LinkedList的相同以及不同之处，以及两者的底层实现（环境OpenJDK 11.0.12）。

    2 两者区别

    在详细介绍两者的底层实现之前，先来简单看一下两者的异同。

    2.1 相同点

    • 两者都实现了List接口，都继承了AbstractList（LinkedList间接继承，ArrayList直接继承）
    • 都是线程不安全的，两者都是不同步的
    • 都具有增删查改方法

    2.2 不同点

    • 底层数据结构不同：ArrayList基于Object[]数组，LinkedList基于LinkedList.Node双向链表
    • 随机访问效率不同：ArrayList随机访问能做到O(1)（实现 RandomAccess），因为可以直接通过下标找到元素，而LinkedList需要从头指针开始遍历，时间O(n)
    • 初始化操作不同：ArrayList无参初始化时初始化为一个空数组，而LinkedList不需要
    • 扩容：ArrayList当长度不足以容纳新元素的时候，会进行扩容，而LinkedList不会
    • 内存空间占用：ArrayList的内存空间占用主要体现在数组结尾会预留一定容量空间，而LinkedList空间花费主要体现在每一个元素都需要消耗比ArrayList更多的空间

    3 ArrayList底层

    3.1 基本结构

    底层使用Object[]数组实现，成员变量如下：

    private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;

    默认的初始化容量为10，接下来是两个空数组，供默认构造方法以及带初始化容量的构造方法使用：

    public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

    下面再来看一些重要方法，包括：

    • add()
    • remove()
    • indexOf()/lastIndexOf()/contains()

    3.2 add()

    add()方法有四个：

    • add(E e)
    • add(int index,E e)
    • addAll(Collection<? extends E> c)
    • addAll(int index, Collection<? extends E> c

    3.2.1 单一元素add()

    先来看一下add(E e)以及add(int index,E eelment)：

    private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) {
        elementData = this.grow();
    }

    elementData[s] = e;
    this.size = s + 1;
}

public boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.size);
    return true;
}

public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }

    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}

    add(E e)实际调用的是一个私有方法，判断是否需要扩容之后，直接添加到末尾。而add(int index,E element)会首先检查下标是否合法，合法的话，再判断是否需要扩容，之后调用System.arraycopy对数组进行复制，最后进行赋值并将长度加1。

    关于System.arraycopy，官方文档如下：

    在这里插入图片描述

    一共有5个参数：

    • 第一个参数：原数组
    • 第二个参数：原数组需要开始复制的位置
    • 第三个参数：目标数组
    • 第四个参数：复制到目标数组的开始位置
    • 第五个参数：需要复制的数目

    也就是说：

    System.arraycopy(elementData, index, elementData, index + 1, s - index);

    的作用是将原数组在index后面的元素“往后挪”，空出一个位置让index进行插入。

    3.2.2 addAll()

    下面来看一下两个addAll()：

    public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        System.arraycopy(a, 0, elementData, s, numNew);
        this.size = s + numNew;
        return true;
    }
}

public boolean addAll(int index, Collection<? extends E> c) {
    this.rangeCheckForAdd(index);
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        int numMoved = s - index;
        if (numMoved > 0) {
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        }

        System.arraycopy(a, 0, elementData, index, numNew);
        this.size = s + numNew;
        return true;
    }
}

    在第一个addAll中，首先判断是否需要扩容，接着也是直接调用目标集合添加到尾部。而在第二个addAll中，由于多了一个下标参数，处理步骤稍微多了一点：

    • 首先判断下标是否合法
    • 接着判断是否需要扩容
    • 再计算是否需要把原来的数组元素“往后挪”，也就是if里面的System.arraycopy
    • 最后把目标数组复制到指定的index位置

    3.2.3 扩容

    上面的add()方法都涉及到了扩容，也就是grow方法，下面来看一下：

    private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity
    上一篇：Au的博客：Java学习笔记——LinkedList插入和删除真的比ArrayLis
    下一篇：没有了