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 = 100000;//测试元素数
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Object> arrList = new ArrayList<Object>();
List<Object> linList = new LinkedList<Object>();
System.out.println("测试元素数:" + max);
// init list
for (int i = 0; i < max; i++) {
arrList.add(i);
linList.add(i);
}
System.out.println("ArrayList访问消耗的时间：" + getTime(arrList) + "ms");
System.out.println("LinkedList访问消耗的时间：" + getTime(linList) + "ms");
System.out.println("\nArrayList删除消耗的时间：" + delTime(arrList) + "ms");
System.out.println("LinkedList删除消耗的时间：" + delTime(linList) + "ms");
System.out.println("\nArrayList插入消耗的时间：" + insertTime(arrList) + "ms");
System.out.println("LinkedList插入消耗的时间：" + insertTime(linList) + "ms");
}
public static long getTime(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < max ; i++) {
int index = Collections.binarySearch(list, list.get(i));
if (index != i) {
System.out.println("ERROR!");
}
}
return System.currentTimeMillis() - time;
}
public static long delTime(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i <list.size(); i++) {
list.remove(i); // 在索引下，逐个删除每个元素
}
return System.currentTimeMillis() - time;
}
public static long insertTime(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < max; i++) {
list.add(i); // 逐个插入 max 个元素
//list.add(i , ""); // 在指定索引下，逐个插入 max 个元素
}
return System.currentTimeMillis() - time;
}
}
下面是这段代码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 <list.size(); i++) {
list.remove(i);
}*/
// 在索引下，从后往前 逐个删除每个元素
/*for (int i = list.size()-1; i >= 0; i--) {
list.remove(i);
}*/
// 在索引下，删除指定段落的元素，奇数位索引段
for (int i = 0; i <list.size(); i++) {
if(i%2==1){
list.remove(i);
}
}
return System.currentTimeMillis() - time;
}这3种情况运行结果如下：
在索引下，从前往后 逐个删除每个元素
测试元素数:100000
ArrayList访问消耗的时间：41ms
LinkedList访问消耗的时间：36210ms
ArrayList删除消耗的时间：412ms
LinkedList删除消耗的时间：3420ms
ArrayList插入消耗的时间：8ms
LinkedList插入消耗的时间：9ms
Process finished with exit code 0
在索引下，从后往前 逐个删除每个元素
测试元素数:100000
ArrayList访问消耗的时间：25ms
LinkedList访问消耗的时间：36412ms
ArrayList删除消耗的时间：9ms
LinkedList删除消耗的时间：9ms
ArrayList插入消耗的时间：11ms
LinkedList插入消耗的时间：9ms
Process finished with exit code 0
在索引下，删除指定段落的元素，奇数位索引段
测试元素数:100000
ArrayList访问消耗的时间：21ms
LinkedList访问消耗的时间：39146ms
ArrayList除消耗的时间：274ms
LinkedList删除消耗的时间：1844ms
ArrayList插入消耗的时间：8ms
LinkedList插入消耗的时间：7ms
Process finished with exit code 0
总结:在集合10万目标测试数，这３种情况下，在删除效率上。
在索引下，从前往后 逐个删除每个元素时，ArrayList较LinkedList快(3420/412=8.300970874)8.3倍；
在索引下，从后往前 逐个删除每个元素时，ArrayList与LinkedList效率均等(9/9=1)；
在索引下，删除指定段落的元素，奇数位索引段时，，ArrayList较LinkedList快(1844/274=6.729927007)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 = 100000;//测试元素数
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Object> arrList = new ArrayList<Object>();
LinkedList<Object> linList = new LinkedList<Object>();
System.out.println("测试元素数:" + max);
System.out.println("ArrayList插入消耗的时间：" + insertTime(arrList) + "ms");
System.out.println("LinkedList插入消耗的时间：" + insertTime(linList) + "ms");
System.out.println("\nArrayList访问消耗的时间：" + getTime(arrList) + "ms");
System.out.println("LinkedList访问消耗的时间：" + getTime(linList) + "ms");
System.out.println("\nArrayList删除消耗的时间：" + delTime_v2(arrList) + "ms");
System.out.println("LinkedList删除消耗的时间：" + delTime_v2(linList) + "ms");
}
public static long insertTime(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < max; i++) {
list.add(i); // 逐个插入 max 个元素
}
return System.currentTimeMillis() - time;
}
public static long getTime(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < max; i++) {
int index = Collections.binarySearch(list, list.get(i));
if (index != i) {
System.out.println("ERROR!");
}
}
return System.currentTimeMillis() - time;
}
public static long delTime_v2(List list) {
long time = System.currentTimeMillis();
while (checkListSize(list)) {
if (list instanceof LinkedList) {
((LinkedList) list).removeFirst();
} else if (list instanceof ArrayList) {
list.remove(0);
}
}
return System.currentTimeMillis() - time;
}
public static boolean checkListSize(List list) {
if (list.size() <= 0)
return false;
else
return true;
}
}
下面是这段代码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。
相关文章
暂无评论...
致力于称为最好的程序员导航网站