ArrayList与LinkedList哪个更占空间？为什么？

1. 引言

在Java编程中，我们经常会用到集合类来存储和操作数据。ArrayList和LinkedList是Java集合框架中两个常用的列表实现类，它们都可以用来存储一组数据，但在底层实现和性能上有所不同。本篇博客将深入探讨ArrayList和LinkedList这两个类的原理和特性，然后从空间占用的角度进行比较，最终得出哪个更占空间的结论。

2. ArrayList的底层实现原理

ArrayList是基于数组实现的动态数组，它可以根据需要自动调整容量。当元素数量超过容量时，自动增加容量以容纳新元素，而当元素数量减少时，自动减小容量以节省内存。下面是ArrayList的部分源代码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
    private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认容量时的空数组
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 最大数组容量

    private transient Object[] elementData; // 存储元素的数组
    private int size; // 元素数量

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

    // 省略其他方法
}

在默认情况下，ArrayList的初始容量为10，当添加第11个元素时，它会自动进行扩容，将当前数组容量扩大为原来的1.5倍，并将元素复制到新的数组中。这种自动增加容量的方式使得ArrayList在添加元素时具有较好的性能，并且可以避免频繁的数组扩容操作。

3. LinkedList的底层实现原理

LinkedList是基于双向链表实现的，它通过链表中的节点来存储元素，并且每个节点都包含了当前元素的引用以及指向前一个节点和后一个节点的引用。下面是LinkedList的部分源代码：

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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;
        }
    }
    
    transient int size = 0; // 元素数量
    transient Node<E> first; // 头节点
    transient Node<E> last; // 尾节点

    // 省略其他方法
}

LinkedList通过头节点和尾节点来管理链表中的元素。当添加元素时，会在链表的尾部添加一个新的节点，并将该节点设置为尾节点。由于LinkedList是双向链表，可以通过尾节点的引用来快速定位到最后一个元素，并且可以在常数时间内进行元素的添加和删除操作。

4. ArrayList与LinkedList的空间占用对比

从ArrayList和LinkedList的底层实现原理可以看出，ArrayList通过动态数组存储元素，而LinkedList通过双向链表存储元素。从存储空间的角度来看，它们存在一些差异。

4.1 ArrayList的空间占用

在ArrayList中，数组的大小会根据实际元素数量进行调整，而不是固定不变的。当元素数量超过数组容量时，ArrayList会自动进行扩容，以容纳更多的元素。扩容会创建一个新的更大的数组，并将原来数组中的元素复制到新数组中。而当元素数量减少时，ArrayList会自动减小容量，以节省内存空间。

因此，ArrayList的空间占用主要取决于当前元素的数量和容量大小。当元素数量接近容量时，ArrayList的空间占用会比较大，因为它需要预留一定的空间用于扩容。而当元素数量较少时，ArrayList的空间占用会比较小，因为它会自动缩小容量以节省内存。

4.2 LinkedList的空间占用

在LinkedList中，每个节点都需要存储当前元素的引用以及指向前一个节点和后一个节点的引用。因此，LinkedList的空间占用与元素的数量成正比。

与ArrayList不同，LinkedList没有固定的容量概念，它可以根据需要动态地添加或删除元素，而不需要进行扩容操作。这意味着LinkedList的空间占用不会因容量的增加而增加，但每个节点的额外引用占用了额外的空间。

5. 总结

经过对ArrayList和LinkedList的底层实现原理和空间占用的分析，可以得出以下结论：

• ArrayList的空间占用主要取决于当前元素的数量和容量大小。当元素数量接近容量时，空间占用会比较大，因为需要预留一定的空间用于扩容。当元素数量较少时，空间占用会比较小，因为会自动缩小容量以节省内存。
• LinkedList的空间占用与元素的数量成正比。每个节点都需要存储当前元素的引用以及指向前一个节点和后一个节点的引用，因此相对于ArrayList会占用更多的空间。

综上所述，ArrayList和LinkedList的空间占用在不同情况下会有所不同。如果对空间占用有较高要求，而对访问和更新操作的性能要求较低，可以选择使用LinkedList；如果对访问和更新操作的性能要求较高，而对空间占用要求较低，可以选择使用ArrayList。

6. 示例代码

下面是一个简单的示例代码，用于演示ArrayList和LinkedList的空间占用：

import jdk.nashorn.internal.ir.debug.ObjectSizeCalculator;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author niuxiangqian
 * @version 1.0
 * @date 2023/8/25 16:03
 **/
public class MemoryUsage {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        for (int i = 0; i < 10000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        System.out.println("ArrayList的空间占用：" + ObjectSizeCalculator.getObjectSize(arrayList) + " bytes");
        System.out.println("LinkedList的空间占用：" + ObjectSizeCalculator.getObjectSize(linkedList) + " bytes");
    }
}

输出结果：

ArrayList的空间占用：216256 bytes
LinkedList的空间占用：400032 bytes

注意我的jdk是zulu-8.jdk，不同的jdk可能不支持ObjectSizeCalculator类，可以用其他方式测量对象大小