从源码分析ArrayList和LinkedList的差别

2019-11-08 01:42:33

字体：大中小

来源：转载

供稿：网友

现在网上对于ArrayList和LinkedList的分析文章非常多，但是基本分析的都有一些错误。所以我想通过源码分析的角度才能正好的理解ArrayList和 LinkedList

ArrayList的基于数组，内部就是一个Object[]的数组。默认的capacity为10。

// 默认的数组容量为10 PRivate static final int DEFAULT_CAPACITY = 10; // Object[]数组 transient Object[] elementData; // 当前数组的大小 private int size; // 数组最大长度 private static final int MAX_ARRAY_SIZE = 2147483639;

ArrayList的add操作，每次都需要检查是否扩容，capacity越小，扩容越频繁，扩容非常耗时。

public boolean add(E arg0) { // 检查是否需要扩容 this.ensureCapacityInternal(this.size + 1); this.elementData[this.size++] = arg0; return true; }

ArrayList扩容机制，当添加一个元素，如果添加元素之后的长度大于原来数组最大长度，就需要扩容，每次扩容的长度为当前最大的一半

private void grow(int arg0) { // 获取数组的长度 int arg1 = this.elementData.length; // 数组长度右移1位（相当于除2） int arg2 = arg1 + (arg1 >> 1); if (arg2 - arg0 < 0) { arg2 = arg0; } // 默认最大长度为2147483639 if (arg2 - 2147483639 > 0) { arg2 = hugeCapacity(arg0); } // 通过Arrays.copyOf方法进行扩容 this.elementData = Arrays.copyOf(this.elementData, arg2); }

LinkedList是一个双链表，有一个firstNode和一个LastNode。

// 链表长度 transient int size; // 头节点 transient LinkedList.Node<E> first; // 尾节点 transient LinkedList.Node<E> last;

LinkedList的add操作：添加一个新的元素时，将创建一个新的Node节点，并设置Node的前节点，设置Node的后节点为null。

void linkLast(E arg0) { LinkedList.Node arg1 = this.last; // 设置arg2的前节点为arg1，后节点为null LinkedList.Node arg2 = new LinkedList.Node(arg1, arg0, (LinkedList.Node) null); // 将arg2节点作为最后一个节点 this.last = arg2; if (arg1 == null) { this.first = arg2; } else { // 设置arg1的后节点为arg2 arg1.next = arg2; } ++this.size; ++this.modCount; }

Node类

private static class Node<E> { E item; LinkedList.Node<E> next; LinkedList.Node<E> prev; Node(LinkedList.Node<E> arg0, E arg1, LinkedList.Node<E> arg2) { this.item = arg1; this.next = arg2; this.prev = arg0; } }

ArrayList的get操作：检查数组是否越界，然后根据下标获取结果

public E get(int arg0) { // 检查是arg0是否超过的数组的长度，超过长度抛出IndexOutOfBoundsException this.rangeCheck(arg0); // 根据下标获取结果 return this.elementData(arg0); }

LinkedList的get操作：根据传入的值进行判断，如果传入的值在0~size/2,那么从头节点开始遍历，如果传入的值在size/2~size范围，那么从尾节点开始遍历。

LinkedList.Node<E> node(int arg0) { LinkedList.Node arg1; int arg2; // arg0是否小于链表的大小的一半 if (arg0 < this.size >> 1) { arg1 = this.first; // 从头节点开始遍历 for (arg2 = 0; arg2 < arg0; ++arg2) { arg1 = arg1.next; } return arg1; } else { arg1 = this.last; // 从尾节点开始遍历 for (arg2 = this.size - 1; arg2 > arg0; --arg2) { arg1 = arg1.prev; } return arg1; } }

ArrayList的remove操作：判断传入的值是否超过数组最大长度，然后获取需要移除的元素的值，再判断被移除的元素是否是最后一位，如果不是，则将传入值之后的所有元素左移一位，最后将最后一位元素设为null。

public E remove(int arg0) { // 检查数组是否越界 this.rangeCheck(arg0); ++this.modCount; // 获取移除的元素值 Object arg1 = this.elementData(arg0); // 判断是否是最后一个元素，arg2等于0，代表最后一个元素 int arg2 = this.size - arg0 - 1; if (arg2 > 0) { // 将所有元素左移一位 System.arraycopy(this.elementData, arg0 + 1, this.elementData, arg0, arg2); } // 设置最后一位值为null，并且size-1 this.elementData[--this.size] = null; return arg1; }

LinkedList的remove操作：先判断是否越界，然后通过get方法获取被移除的节点，判断是否是first节点和last节点，并设置移除节点所有属性为null和将被移除的节点前后节点连接。

// 在操作unlink之前需要通过get方法获取被移除的节点E unlink(LinkedList.Node<E> arg0) { Object arg1 = arg0.item; // 获取移除值的后节点 LinkedList.Node arg2 = arg0.next; // 获取移除值的前节点 LinkedList.Node arg3 = arg0.prev; // 判断移除的是否是第一个节点，如果是就讲移除节点的后节点设置为第一个节点 if (arg3 == null) { this.first = arg2; } else { arg3.next = arg2; arg0.prev = null; } // 判断移除的是否是最后一个节点 if (arg2 == null) { this.last = arg3; } else { arg2.prev = arg3; arg0.next = null; } arg0.item = null; --this.size; ++this.modCount; return arg1; }

比较ArrayList和LinkedList进行add，get，remove的速度

add：当数据小于5万以下，通过add操作，LinkedList比ArrayList速度明显快，但当数据逐渐再增大，ArrayList的数组明显比LinkedList快很多很多。

原因分析：ArrayList的默认capacity的值为10，当插入大量数据时（大约5万条），ArrayList需要多次扩容，所以影响ArrayList的速度。但是当数据量再逐渐增大，ArrayList的扩容大小按指数增张，后面扩容的次数会越少，然而每次扩容的容量却越大，所以导致最终ArrayList的总体速度反而更快。单纯从add操作上看，ArrayList的速度比LinkedList的速度快，但是因为ArrayList前期由于需要扩容的次数太多，从而拖慢了ArrayList的速度。

解决方案：使用ArrayList数据量很大时，最好指定ArrayList的数组大小。

get：ArrayList的get操作明显快于LinkedList的get操作。

原因分析：ArrayList通过下标直接获取值，而LinkedList需要通过移动指针（很费时）来获取对应值，每取一个数都要从头或者从尾部开始移动指针来获取对应的值。

remove：在数据量小的情况下，LinkedList的remove速度明显比ArrayList快，但是一旦数据量非常的大，并且删除的数据都是随机分布时，LinkedList的速度会非常的慢。

原因分析：ArrayList的remove删除元素后，需要左移一位（比较耗时），但是LinkedList的remove操作，先通过get方法获取指定的值，因为get方法需要通过移动指针来获取指定值，一旦数据量非常大时，get操作非常的耗时。所以导致一旦数据量很大，并且随机删除元素时，LinkedList的速度反而很慢。数据量小的情况下，LinkedList的remove的速度要快。

上一篇：Anaconda安装二三事

下一篇：ConcurrentHashMap 探索