ArrayList和LinkedList的对比

╰+哭是因爲堅強的太久メ 2022-02-20 10:09 262阅读 0赞

List数据结构在实际开发中是非常常见的，其中Arraylist和LinkedList又是这种数据结构中最常见的，本篇文章将会从不同角度来记录讲解这两种list的实现方式及优缺点，以及在实际开发中该如何去选择

## ArrayList的实现 ##

当我们需要去初始化一个ArrayList的时候，会运行一下代码：

List list = new ArrayList();

当运行这行代码的时候发生了什么呢？仅仅只是初始化了一个object数组，并且是一个空数组。当然，我们也可以自己指定这个初始化的数组的大小。

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

我们也可以通过源码的注释发现，elementData在初始化的时候是一个空的数组，当添加第一个元素的时候，将会将数组的大小扩充至默认的大小（默认大小为10）：

/**
      * The array buffer into which the elements of the ArrayList are stored.
      * The capacity of the ArrayList is the length of this array buffer. Any
      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
      * will be expanded to DEFAULT_CAPACITY when the first element is added.
    */
    transient Object[] elementData; // non-private to simplify nested class access

接下来我们再看当我们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);
    }

由上面的代码可知，当我们添加第一个元素的时候，会将list的大小扩充到10，当容量不够时，将会再次进行扩充，扩充大小为1.5倍。值得注意的是，**每次进行扩充操作的时候，都是先初始化一个目标大小的数组，再将原数组中的元素copy进入新的数组**。

下面我们通过一段代码来验证一下：

public static void main(String[] args) throws Exception {
    	    ArrayList list = new ArrayList();
    	    Class<?> clazz = Class.forName("java.util.ArrayList");
    	    Field field = clazz.getDeclaredField("elementData");
    	    field.setAccessible(true);
    	    System.out.println("初始化大小：" + ((Object[]) field.get(list)).length);
    	    list.add(-1);
    	    System.out.println("添加1个元素后大小：" + ((Object[]) field.get(list)).length);
    	    for (int i = 0; i < 10; i++) {
    	        list.add(i);
    	    }
    	    System.out.println("添加11个元素后大小：" + ((Object[]) field.get(list)).length);
    }
    
    运行结果如下：
    
    初始化大小：0
    添加1个元素后大小：10
    添加11个元素后大小：15

## LinkedList的实现 ##

LinkedList的底层实现为链表的数据结构。链表是由一个一个的node节点组成的：

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

这里可以看出每一个节点都会记录上一个节点和下一个节点的地址。  
当向LinkedList中插入元素时，只需要将这个节点和链表的最后一个节点连接起来即可：

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

## ArrayList和LinkedList在时间复杂度上的对比 ##

**1. 在读方面**

由于ArrayList存在角标，所以在随机读的时候，毫无疑问，Arraylist完胜LinkedLis，但是在实际开发中，大多数情况要求的都是遍历循环，在这种业务场景下两者的效率是在一个数量级上的。但是这边读取方式不同，影响也是巨大的，以下是两种list较为优化的遍历读取心得：

1. ArrayList遍历循环的时候，直接使用普通的for循环的效率更加高一些
    2. ArrayList在for循环的时候，如果可以将size = list.size()提取出来，也会起到一定的优化作用
    3. LinkedList在遍历循环的时候要使用for each循环或者迭代器，因为这两种方式的循环都是指针，
       而使用普通的for循环每次循环都需要从头开始，当数据量较大时，效率极低。

**2. 在写方面**

在写方面，综合来看LinkedList是要优于ArrayList的，原因如下：

*  Arraylist的底层是数组，当需要将数据写到数组的非末尾位置的时候，数组的其他元素需要移位
 *  数组的容量是初始化就固定的，当元素数量大于数组容量时，就会进行扩容，扩容要求初始化一个新的数组，并将老数组中的元素copy到新的数组中
 *  由于数组要求是一段连续的内存空间，所以可能会涉及到重新寻找足够大的内存空间以存放新的数组

由此可以看出，在写方面，特别是非末尾位置写，LinkedList是要优化于Arraylist的。

## ArrayList和LinkedList在空间复杂度上的对比 ##

*  LinkedList除了需要存储本身的数据，还需要记录各节点之间的连接信息，所以LinkedList对空间的消耗主要体现在每一个元素上面
 *  ArrayList由于底层是一个数组结构，所以可能会存在元素未填充满而导致的内存空间的浪费
 *  ArrayList在空间扩容的时候，需要初始化新的数组，也是对空间的一种浪费（需要等待垃圾回收回收掉原来无效的数组）

下面我们通过一个小demo来看一下ArrayList和LinkedList分别添加1000条数据后，他们各占用的内存空间大小：

public static void main(String[] args) throws Exception {
         //用于计算对象偏移量的类
         ClassIntrospector cIntrospector = new ClassIntrospector();
         ArrayList arrayList = new ArrayList();
         System.out.println("添加元素前ArrayList大小：" + cIntrospector.introspect(arrayList).getDeepSize());
         for (int i = 0; i < 1000; i++) {
             arrayList.add(i);
         }
         System.out.println("添加元素后ArrayList大小：" + cIntrospector.introspect(arrayList).getDeepSize());
         arrayList.trimToSize();
         System.out.println("添加元素后并进行trim操作后ArrayList大小：" + cIntrospector.introspect(arrayList).getDeepSize());
         LinkedList linkedList = new LinkedList();
         for (int i = 0; i < 1000; i++) {
             linkedList.add(i);
         }
         System.out.println("添加元素后LinkedList大小：" + cIntrospector.introspect(linkedList).getDeepSize());
     }
     
    运行结果如下：
    添加元素前ArrayList大小：40
    添加元素后ArrayList大小：20976
    添加元素后并进行trim操作后ArrayList大小：20040
    添加元素后LinkedList大小：40032

由结果可以看出ArrayList在trimToSize之前确实有一部分空间的浪费，但是总体来说，占用的总的空间要小于LinkedList。  
上面使用的计算一个对象的大小的方式可以参考[jvm两种方式获取对象所占用的内存][jvm]

## 总结 ##

1.  当我们知道将要往List中添加的元素的数量的时候，并且后期全为读操作的时候，使用ArrayList更好，这里可以在初始化ArrayList的时候就指定容量。
2.  如果写操作比较频繁的时候，使用LinkedList是更好的选择。
3.  如果需要遍历操作，ArrayList使用普通for循环效果更佳，可以使用size = list.size()进行优化。
4.  如果需要遍历操作，LinkedList使用for each循环或者迭代器更好，因为这样不需要每次都从头开始。
5.  如果是遍历操作，两种list的效率相差不大。
6.  在总空间占用上ArrayList略占优势。
7.  但是ArrayList需要完整的空间，而LinkedList则不需要。

[jvm]: https://blog.csdn.net/mazhen1991/article/details/79519958