数组与链表，数组少性能到底差多少？

作者：活在信息时代 2023-03-01 07:37:10开发 前端 所谓数组，链表就是到底在内存中连续存储多个元素的结构，在内存中的差多分配也是连续的。数组中的数组少元素通过数组下标进行访问，数组下标从0开始。链表

 本文转载自微信公众号「活在信息时代」，到底作者活在信息时代。差多转载本文请联系活在信息时代公众号。数组少

同为基础的链表数据结构，数组与链表是到底最为常用的两个大类之一。

所谓数组，差多就是数组少在内存中连续存储多个元素的结构，在内存中的链表分配也是连续的。数组中的到底元素通过数组下标进行访问，数组下标从0开始。

而链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

根据两者的不同特点，我们可以看到，对于数组而言，数据是可以直接访问的，也就是说如果我想访问排序为6的数据，只需要眼看着访问地址为6的内存，就可以得到结果了。

而如果想访问链表中排序为6的数据，则需要从头开始，查找到第六个，才能获取到结果。

而插入数据的话，在数组中插入一条数据，则需要把插入之后的数据全部往后挪一遍。

而对于链表来说，插入一条数据，只需要将要插入位置的链解开，将前一节的下一个指针指向插入的节点，而将新节点的下一个指针指向原来的后一节就行了。非常简单。

那么，两者的效率空间会差多少呢？我们可以写个代码来验证一下。

我们知道，在Java中，ArrayList是基于数组实现的List，而LinkedList则是基于链表而实现的。那么，我们就可以写一段代码来测试一下他们的效率了。

插入代码如下：

数组：

List<Integer> arrayList = new ArrayList<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i< index; i++) { 
arrayList.add(0, i);
}
long end = System.currentTimeMillis();
System.out.println("数组插入耗时: "+ (end - start));

链表：

Long start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<Integer>();
for (int i =0; i< index; i ++) { 
linkedList.add(0, i);
}
Long end = System.currentTimeMillis();
System.out.println("链表插入耗时: "+ (end - start));

查询代码如下：

数组：

List<Integer> arrayList = new ArrayList<Integer>();
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<Integer> linkedList = new LinkedList<Integer>();
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的情况下，结果如下：

可见差距还是很明显的。

责任编辑：武晓燕 来源： 今日头条 数组链表性能

(责任编辑：综合)