ArrayList 与 LinkedList 比较（实现方式）

 

        欢迎访问我的个人博客

         面试的时候，经常会有面试官提问Collection接口下面实现类的区别，以及各自适用场景，不少人都能答出来：ArrayList基于数组实现，善于随机访问和遍历集合，做随机位置插入和删除性能较差，而ArrayList基于链表结构实现（双向链表），在做随机位置插入时性能较好于ArrayList，在做遍历和随机访问时性能较差。但很多人不知道到底为什么基于数组实现随机访问就快？任意位置插入性能就差？而基于链表实现的正好相反呢？

         要弄清楚这个问题，必须要清楚其实现方式，最好的办法就是去看源码，这是一种好的

学习习惯。

从上面图可以看到List接口下的所有实现类和父接口，其中当然包括本文介绍的主角儿ArrayList,和LinkedList，既然是实现自同一接口，那么他们的规范自然是一样的。

         如上图，因为源码注释太多，看着烦躁，这里我用Ctrl+o可以看到List接口下面的所有方法，接下来，我们来看看他们各自的实现的代码吧！

         首先我们看ArrayList,在类中有个Object[] elementData,可以想到他是用来存放Arraylist中的数据的。

那么，它是怎样对数据进行增删改查操作的？

1 2 3 4 5

public boolean add(E e) {         ensureCapacityInternal(size + 1);  // Increments modCount!!         elementData[size++] = e;         return true; }

 

这是add方法，主要是将e赋值给数组，将数组长度加一，ensureCapacityInternal里面主要是做一些逻辑判断，请看grow方法

1 2 3 4 5 6 7 8 9 10 11

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

 

 

Arrays.copyOf(elementData, newCapacity);这行代码非常关键，他是影响ArrayList插入性能的主要因素，当数组下表超过数组长度时会调用这个方法，调用Arrays.copyOf的方法时会重新copy构建一个新的数组,会消耗大量的资源，导致性能变的很差。

下面看看随机插入add(int index, E element)

1 2 3 4 5 6 7 8 9

public void add(int index, E element) {         rangeCheckForAdd(index);            ensureCapacityInternal(size + 1);  // Increments modCount!!         System.arraycopy(elementData, index, elementData, index + 1,                          size - index);         elementData[index] = element;         size++; }

 

此处更是不消多说，就是copy copy copy，大量的数组移动，导致性能底下。remove方法与add方法实现类似.

再来看看随机访问和遍历，get方法非常简单

1 2 3 4

public E get(int index) {         rangeCheck(index);         return elementData(index); }

 

直接指向数组下标位置的元素返回，当然是最快的，遍历亦是如此。

再来看看LinkedList的内部实现吧

 

内部有两个Node对象，一个指向集合第一个，一个指向最后一个，Node内部代码如下

1 2 3 4 5 6 7 8 9 10 11

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

 

每一个Node都有next和prev两个对象，相互关联这就形成了一条链子，所以这个叫做链表结构（双向），用网上的一个图片。

 

再来看看他们实现add和remove的方法吧！

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public boolean add(E e) {         linkLast(e);         return true; } 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++; }

 

从上面代码不难发现，普通的add会调用linkLast,linkdLast方法内部会新建一个Node对象，将要存储的值放入node中，同时把当前的node绑定到集合最末端，时间复杂度为O(n).

再看指定位置的插入，add(int index, E element)方法。

1 2 3 4 5 6 7 8

public void add(int index, E element) {         checkPositionIndex(index);            if (index == size)             linkLast(element);         else             linkBefore(element, node(index)); }

 

当需要插入的位置为集合大小时，可以直接插入集合尾部，否则，则需要找到指定位置的下标然后修改他们next、prev的指向，这里会有一个遍历，JDK对其做了优化，不同位置从两端遍历，这样让遍历的查找时间降到最低。代码如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

 

remove与add逻辑类似。

 

总结一下，ArrayList得其天赋是数组，数组在随机访问时的速度是与生俱来的，而其软肋就是数组是固定的，大小固定，位置固定，所以你做新增（特别是中间段的新增或者是长度已达目前初始大小时），删除会频繁移动数组，导致性能底下。

而在LinkedList里面，由于他使用双向链表结构实现，那么新增和删除，只需要修改相应的指向就行了，在中间位置插入会比在末尾插入性能要差点，在随机访问时，由于需要遍历，所以速度逊于ArrayList,在做遍历的时候也是一样，使用迭代器可以缓解这个问题。

         值得一提的时，假设我需要一个长度为固定数量S的集合，默认向里面add数据，给ArrayList赋予初始初始容量S，那么ArrayList插入的性能会优于LinkedList，请看测试代码和运行结果。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

public static void main(String[] args) {         int size=10000000;         testArraylistAdd(size);         testLikedlistAdd(size);     }        static void testArraylistAdd(int size) {         long t1 = System.currentTimeMillis();         List<Integer> list = new ArrayList<Integer>(size);         for (int i = 0; i < size; i++) {             list.add(i);         }         long t2 = System.currentTimeMillis();         System.out.println("测试" + size + "条数据，插入ArrayList所花费时间 为：" + (t2 - t1));     }        static void testLikedlistAdd(int size) {         long t1 = System.currentTimeMillis();         List<Integer> list = new LinkedList<Integer>();         for (int i = 0; i < size; i++) {             list.add(i);         }         long t2 = System.currentTimeMillis();         System.out.println("测试" + size + "条数据，插入LinkedList所花费时间 为：" + (t2 - t1));     }

 

测试10000000条数据，插入ArrayList所花费时间 为：78

测试10000000条数据，插入LinkedList所花费时间 为：4738

主要是因为初始时指定了数组长度，插入时不需要频繁移动数组，所以速度才会优于LinkedList

评论

2 楼 freezingsky 2014-08-18  

这种问题虽然也被问过不少次，但从来没有去看代码的实现，如果非要讲二者之间有何不同，其实数据结构这门课就已经说得够清楚了。

1 楼 hngmduyi 2014-08-18