这个问题的答案确实是不一定哦,我以前也在书上看到过这道题,做过笔记:你要考虑到这个问题,首先要查找被插入或者删除的位置,这个我们往往忽略掉了。
其实数组在计算机中的存储是一块连续的内存,通过索引访问;而链表则是不连续的存储单元,通过指针关联,这个基本知识大家都明白,数组中执行插入操作时,将插入点之后的元素依次后移一位,然后将新元素插入到腾出的位置。而进行删除操作时则是将指定位置的元素删掉,之后的元素依次前移一位,这看起来是是一个比较繁琐的过程,而对于链表,处理方式就很简单了,需要在某个节点之后插入节点的时候,只需要将新节点的后继指向该节点原本的后继,再将该节点的后继指向新节点即可,删除节点则更为简单,只需要让被删借点的前驱指向他的后继即可。 稍微思考一下,所有人都会认为数组在这方面的效率很差,但是这份比较从根本上说来说是不公平的,无论是链表还是数组,插入和删除都要两个步骤,查找位置,和插入删除,我们只关注了后者,那查找的实践却没有计算在内,对于数组来说查找位置就是查找索引的位置,这在计算机的计算中可以忽略不计,而链表只要找到了位置,插入和删除也就差不多完成了,所以二者的侧重点有所不同。下面是我写的代码验证一下二者的区别:就是随机访问10000次所需要的时间 package com.heima.jianjian;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class TimeTest
{
public static void main(String[] args)
{
long[] timeBegin = new long[2];// 记录开始时间
long[] timeEnd = new long[2];
Integer[] ia = new Integer[5000];
for (int i = 0; i < 5000; i++)
{
ia = i;
}
int tempi;
Random r = new Random();
// 对ArrayList数组进行随机访问
List list = new ArrayList(Arrays.asList(ia));
timeBegin[0] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));
}
timeEnd[0] = System.currentTimeMillis();
// 对LinkedList进行随机访问
list = new LinkedList(Arrays.asList(ia));
timeBegin[1] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));
}
timeEnd[1] = System.currentTimeMillis();
System.out.println(timeEnd[0] - timeBegin[0]);
System.out.println(timeEnd[1] - timeBegin[1]);
}
}
输出的结果分别是:5 和51毫秒 ; 希望能对你有所帮助,大家一起加油! |