面试题 ArrayList与LinkedList的区别

ArrayList与LinkedList的区别（Java基础面试题）

面试官问你这个题的关键，是为了考察你的数据结构功底，理解及深入程度。

此处ArrayList和LinkedList是Java语言实现的数据结构，如果你对数组和链表有了解，那这个问题就是简易的。

进入正题，总结几点：

1. ArrayList的实现是基于数组来实现的，LinkedList的基于双向链表来实现。这两个数据结构的逻辑关系是不一样，当然物理存储的方式也会是不一样。 

2. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

3. 对于随机访问，ArrayList要优于LinkedList。

4. 对于插入和删除操作，LinkedList优于ArrayList。

4. 对于插入和删除操作，LinkedList优于ArrayList（理论上），实际并非如此（实际上ArrayList不论是插入还是删除效率，在元素数量趋多时，都是要优于LinkedList的），因这其中涉及数组与链表在元素操作方式、时间与空间上的复杂度计算问题，所以具体问题须具体分析和佐证。

我们假设现在有10万个元素放置在集合中，在这种情况下对集合做元素操作。

下面一段代码来说明ArrayList和LinkedList在做数据查询、插入、删除时的性能比较

package test; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; public class P2 { public static int max = ;//测试元素数 public static void main(String[] args) { // TODO Auto-generated method stub List 

下面是这段代码3次运行的结果：

补充（update 2020年 05月 03日 星期日 18:11:53 CST）：

为了佐证ArrayList与LinkedList在做删除上的效率，在上面代码，仅修改delTime方法下，另测了这3种情况。

public static long delTime(List list) { long time = System.currentTimeMillis(); // 在索引下，从前往后 逐个删除每个元素 /*for (int i = 0; i 
  
    = 0; i--) { list.remove(i); }*/ // 在索引下，删除指定段落的元素，奇数位索引段 for (int i = 0; i 
    
  

这3种情况运行结果如下：

在索引下，从前往后 逐个删除每个元素 测试元素数: ArrayList访问消耗的时间：41ms LinkedList访问消耗的时间：36210ms ArrayList删除消耗的时间：412ms LinkedList删除消耗的时间：3420ms ArrayList插入消耗的时间：8ms LinkedList插入消耗的时间：9ms Process finished with exit code 0 在索引下，从后往前 逐个删除每个元素 测试元素数: ArrayList访问消耗的时间：25ms LinkedList访问消耗的时间：36412ms ArrayList删除消耗的时间：9ms LinkedList删除消耗的时间：9ms ArrayList插入消耗的时间：11ms LinkedList插入消耗的时间：9ms Process finished with exit code 0 在索引下，删除指定段落的元素，奇数位索引段 测试元素数: ArrayList访问消耗的时间：21ms LinkedList访问消耗的时间：39146ms ArrayList除消耗的时间：274ms LinkedList删除消耗的时间：1844ms ArrayList插入消耗的时间：8ms LinkedList插入消耗的时间：7ms Process finished with exit code 0 总结:在集合10万目标测试数，这３种情况下，在删除效率上。 在索引下，从前往后 逐个删除每个元素时，ArrayList较LinkedList快(3420/412=8.)8.3倍； 在索引下，从后往前 逐个删除每个元素时，ArrayList与LinkedList效率均等(9/9=1)； 在索引下，删除指定段落的元素，奇数位索引段时，，ArrayList较LinkedList快(1844/274=6.)6.7倍； 

==================================以上博文内容作废,(update 2020年 05月 23日 星期六 23:21:13 CST)======

package com.example.application_demo2; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; public class P7 { public static int max = ;//测试元素数 public static void main(String[] args) { // TODO Auto-generated method stub ArrayList 

下面是这段代码3次运行的结果：

为了佐证ArrayList与LinkedList在做删除上的效率，在上面代码，仅修改delTime_v2方法下，另测了这两种情况。

public static long delTime_v2(List list) { long time = System.currentTimeMillis(); while (checkListSize(list)) { // 1.在集合中，从前往后顺序 逐个删除元素 if (list instanceof LinkedList) { ((LinkedList) list).removeFirst();//从头部删除元素 } else if (list instanceof ArrayList) { list.remove(0);//从头部删除元素 } //2.在集合中，从后往前顺序 逐个删除元素 /*if (list instanceof LinkedList) { ((LinkedList) list).removeLast();//从尾部删除元素 } else if (list instanceof ArrayList) { list.remove(list.size() - 1);//从尾部删除元素 }*/ } return System.currentTimeMillis() - time; }

这两种情况运行结果如下：

总结：理论是正确的。

１. 对于随机访问，ArrayList要优于LinkedList。

２. 对于插入和删除操作，LinkedList优于ArrayList。