ArrayList、LinkedList哪家强，据说90%人都不知道

青旅半醒 2023-02-27 12:28 102阅读 0赞

写代码的时候很经常就会用到List集合，但是很多时候我看到童鞋们都是用ArrayList来作为实现类，很少用LinkedList，鉴于这两个集合使用频率特别高，所以老师给童靴们分析一下，他们在不同场景下面效率，谁低谁高。

学过数据结构的同学都知道，ArrayList采用的是线性表存储，LinkedList采用的链表存储，关于两则之前的区别，童鞋们可以自行了解。

一、ArrayList与LinkedList

我们主要研究以下几点：

1.  ArrayList多次扩容数组，对性能影响情况？
2.  添加和删除哪一个更加高效？
3.  各自内存使用情况，谁高谁低？

1.1、我们先来测试一下第一点，代码如下所示：

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int size = 1000 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("ArrayList----time:" + (time2 - time1));
    }
    
    结果：ArrayList----time:2493
    
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(1100 * 10000);
        int size = 1000 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("ArrayList----time:" + (time2 - time1));
    }
    结果：ArrayList----time:560
    
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        int size = 1000 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("LinkedList----time:" + (time2 - time1));
    }
    结果：LinkedList----time:6302

> 结论：在数据量足够大的情况下，设置ArrayList的初始值要比没设置的添加速度快。但是初始值n并不是越大越好，如果设置过大，有可能会造成内存溢出，反而添加速度更慢。
> 
> 但是如果ArrayList数据量特别小的情况下，二则相差无几，当然对计算机而言，如果没触发扩容二者都一样，如果触发了，就要比对谁触发的次数多，移动的数据量大。
> 
> 相对ArrayList而言，LinkedList的添加速度慢，慢了差不多三倍。

1.2、添加和删除哪一个更加高效？

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int size = 10 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("add----time:" + (time2 - time1));
        for (int i = 0; i < list.size(); i++) {
            list.remove(i);
            i--;
        }
        Long time3 = System.currentTimeMillis();
        System.out.println("remove----time:" + (time3 - time2));
    }
    
    结果：
    add----time:5
    remove----time:566
    
    // LinkedList正序坐标删除
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        int size = 10 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("add----time:" + (time2 - time1));
        for (int i = 0; i < list.size(); i++) {
            list.remove(i);
            i--;
        }
        Long time3 = System.currentTimeMillis();
        System.out.println("remove----time:" + (time3 - time2));
    }
    结果：
    add----time:4
    remove----time:3
    
    // LinkedList逆序坐标删除
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        int size = 10 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("add----time:" + (time2 - time1));
        for (int i = 0; i < list.size(); i++) {
            list.remove(list.size() - i - 1);
            i--;
        }
        Long time3 = System.currentTimeMillis();
        System.out.println("remove----time:" + (time3 - time2));
    }
    结果：
    add----time:6
    remove----time:3
    
    // LinkedList逆序对象删除
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        int size = 10 * 10000;
        Long time1 = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Long time2 = System.currentTimeMillis();
        System.out.println("add----time:" + (time2 - time1));
        for (int i = 0; i < list.size(); i++) {
            Integer integer = list.get(list.size() - i - 1);
            list.remove(integer);
            i--;
        }
        Long time3 = System.currentTimeMillis();
        System.out.println("remove----time:" + (time3 - time2));
    }
    结果：
    add----time:6
    remove----time:12107

ArrayList因为添加触发到扩容，最终执行的是System.arraycopy本地方法，执行速度相对较快，但删除需要进行数据移动，所以执行效率低。

LinkedList正序坐标删除和逆序坐标删除，时间效率都一样，逆序坐标删除是因为程序做了特殊处理，但是如果是逆序对象删除的话，运行效率就会特别差，原理后面再介绍。

1.3、内存使用情况如何？

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int size = 100 * 10000;
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        System.out.println("memory:"+ RamUsageEstimator.humanSizeOf(list));
    }
    结果：memory:19.9 MB
    
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        int size = 100 * 10000;
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        System.out.println("memory:"+ RamUsageEstimator.humanSizeOf(list));
    }
    结果：memory:38.1 MB

同等size大小的集合，显然LinkedList要比ArrayList更吃内存，所以如果是超大集合存储的话，要留意内存使用情况。

二、源码分析

2.1、ArrayList源码

2.1.1、add()

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    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);
    }
    
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
        return copy;
    }

ArrayList的add()方法本质就是数组中设置值，这没什么好说的，重点在于扩容，当数组size达到扩容标准后，就会触发System.arraycopy进行数组复制，这对时间和空间上都会有一定的影响。

2.1.2、remove()

// 坐标删除
    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;
    }
    
    // 对象删除
    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;
    }
    
    private void fastRemove(int index) {
        modCount++;
        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
    }

ArrayList的remove如果是对象删除的话也是需要循环的，删除之后还需要再执行一次System.arraycopy复制操作，所以在时间和空间上面效率都很差。如果是坐标删除的话，就不需要进行循环，直接System.arraycopy即可。

2.2、LinkedList原理

2.2.1、add()

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

LinkedList的add()方法没什么可介绍的，就是链表节点的添加。

2.2.2、remove()

// 坐标删除
    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;
        }
    }
    
    // 对象删除
     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;
        }

LinkedList不管是坐标删除还是对象删除，第一步都是循环找到需要删除的节点，然后删除该节点的指向，不同的是坐标删除分为前后两种循环，所以链表从头删除和从尾删除，时间效率都是一样的。

总结

> 介绍到这边，想必童靴们也知道他们之间的区别了，总结一下就是，如果高频添加后删除，建议使用LinkedList，如果主要是查询，那最好使用ArrayList。
> 
> 使用ArrayList如果能设置数组初始值，最好设置初始值，使用LinkedList删除，最好从头或者从尾开始坐标删除，如果是对象删除，最好从头部开始删除。

**代码无非增删改查，关注老师给你Coding**

![aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zdTUxaWJiaWF5dnhzZEkwODVpY1JNWWljTDVFaWIwMVkxZ0drcTVNdWxMdXJ6T0QzU251V2oydzA5cjgwSnBTdm5xSTJtV2g0QUJ5RmhJTnZ1bHhwS2I2b1JBLzY0MD93eF9mbXQ9anBlZw][]

**林老师带你学编程**：[https://wolzq.com][https_wolzq.com]

[aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zdTUxaWJiaWF5dnhzZEkwODVpY1JNWWljTDVFaWIwMVkxZ0drcTVNdWxMdXJ6T0QzU251V2oydzA5cjgwSnBTdm5xSTJtV2g0QUJ5RmhJTnZ1bHhwS2I2b1JBLzY0MD93eF9mbXQ9anBlZw]: /images/20230209/7233984608f64e30a78250d1c14e5d6d.png
[https_wolzq.com]: https://wolzq.com/