增加和删除数据时，为什么LinkedList通常比ArrayList快？ |
您所在的位置：网站首页 › a330和a321哪个速度快 › 增加和删除数据时，为什么LinkedList通常比ArrayList快？ |
增加和删除数据时，为什么LinkedList通常比ArrayList快？
|
实验 首先我们做一个实验：将10万条String类型的数据分别添加到一个LinkedList和一个ArrayList中，且每次都是在第0位（即首位）插入数据，代码如下 结果是LinkedList比ArrayList要快： ArrayList平均用了500毫秒，而LinkedList平均只用了15毫秒；进行多次实验你就会发现，添加的数据量越大，LinkedList的速度优势越明显，这是为什么呢？ import org.junit.Test; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListAddTest { List arrList = new ArrayList(); List lnkList = new LinkedList(); void add(List list) { long startTime = System.currentTimeMillis(); System.out.println("开始的时间：" + startTime); for (int i = 0; i < 100000; i++) { list.add(0, String.valueOf(i)); } long endTime = System.currentTimeMillis(); System.out.println("结束的时间：" + endTime); System.out.println("总耗时：" + (endTime - startTime)); } @Test public void addTimeTest() { add(arrList); // 开始的时间：1487783199226 // 结束的时间：1487783199741 // 总耗时：515 add(lnkList); // 开始的时间：1487783199741 // 结束的时间：1487783199756 // 总耗时：15 } }分析 首先，阅读JDK的文档，我们从中可以知道，ArrayList实际上是一个可变长的数组，LinkedList则是由相互引用的节点组成的双向链表 紧接着我们就要知道，在增加数据时LinkedList和ArrayList分别在底层发生了什么？于是略读JDK源码我们就可以得出：
● 既然LinkedList是一个由相互引用的节点组成的双向链表，那么当把数据插入至该链表某个位置时，该数据就会被组装成一个新的节点，随后只需改变链表中对应的两个节点之间的引用关系，使它们指向新节点，即可完成插入（如下图）；同样的道理，删除数据时，只需删除对应节点的引用即可
● 而ArrayList是一个可变长数组，插入数据时，则需要先将原始数组中的数据复制到一个新的数组，随后再将数据赋值到新数组的指定位置（如下图）；删除数据时，也是将原始数组中要保留的数据复制到一个新的数组
结论 因此，在添加或删除数据的时候，ArrayList经常需要复制数据到新的数组，而LinkedList只需改变节点之间的引用关系，这就是LinkedList在添加和删除数据的时候通常比ArrayList要快的原因
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
|
图片新闻 |
|
专题文章 |