同为基础的数据结构,数组与链表是最为常用的两个大类之一。
所谓数组,就是在内存中连续存储多个元素的结构,在内存中的分配也是连续的。数组中的元素通过数组下标进行访问,数组下标从0开始。
![](http://dingyue.ws.126.net/2023/0228/d42a6ef8j00rqsq0q000ac000hs005em.jpg)
而链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。
![](http://dingyue.ws.126.net/2023/0228/645b605cj00rqsq0q000kc000hs004im.jpg)
根据两者的不同特点,我们可以看到,对于数组而言,数据是可以直接访问的,也就是说如果我想访问排序为6的数据,只需要眼看着访问地址为6的内存,就可以得到结果了。
而如果想访问链表中排序为6的数据,则需要从头开始,查找到第六个,才能获取到结果。
而插入数据的话,在数组中插入一条数据,则需要把插入之后的数据全部往后挪一遍。
![](http://dingyue.ws.126.net/2023/0228/f33d609ej00rqsq0q000oc000hs008hm.jpg)
而对于链表来说,插入一条数据,只需要将要插入位置的链解开,将前一节的下一个指针指向插入的节点,而将新节点的下一个指针指向原来的后一节就行了。非常简单。
![](http://dingyue.ws.126.net/2023/0228/9ae4a743j00rqsq0q000ac000hs0053m.jpg)
那么,两者的效率空间会差多少呢?我们可以写个代码来验证一下。
我们知道,在Java中,ArrayList是基于数组实现的List,而LinkedList则是基于链表而实现的。那么,我们就可以写一段代码来测试一下他们的效率了。
插入代码如下:
数组:
ListarrayList =newArrayList
longstart = System.currentTimeMillis();
for(inti = 0; i< index; i++) {
arrayList.add(0, i);
long end = System.currentTimeMillis();
System.out.println("数组插入耗时: "+ (end - start));
链表:
Long start = System.currentTimeMillis();
List
linkedList = new LinkedList
for (int i =0; i< index; i ++) {
linkedList.add(0, i);
Long end = System.currentTimeMillis();
System.out.println("链表插入耗时: "+ (end - start));
查询代码如下:
数组:
List
arrayList = new ArrayList
for (int i = 0; i< index; i++) {
arrayList.add(i);
long start = System.currentTimeMillis();
for (int i : arrayList) {
int j = arrayList.get(i);
long end = System.currentTimeMillis();
System.out.println("数组查询耗时: "+ (end - start));
链表:
List
linkedList = new LinkedList
for (int i =0; i< index; i ++) {
linkedList.add(i);
Long start = System.currentTimeMillis();
for (int i : linkedList) {
linkedList.get(i);
Long end = System.currentTimeMillis();
System.out.println("链表查询耗时: "+ (end - start));
在将index设置为100000的情况下,结果如下:
![](http://dingyue.ws.126.net/2023/0228/37f59d2ej00rqsq0q000nc000e8007om.jpg)
可见差距还是很明显的。
喜欢本文的话,欢迎关注活在信息时代哦:)
热门跟贴