说到ArrayList和LinkedList我们不得不放出下面的这张图来帮助我们更好的了解他们的区别。
图片来自网络
从图中我们已经可以看出他们的区别了
ArrayList是顺序结构，所以定位很快，我们可以根据下标可以很容易的找到我们的想要的位置，但在插入数据时我们要移动后边的所有数据，所以插入数据很慢。
而LinkedList 是链表结构，像串起来的珠子，我们只能一个个的顺着那条虚拟的线去找，虽然不能快速的查找，但是插入数据的时候只需要更改相应位置前后的连接，所以插入数据很快。
这时候大部分人会想当然的说LinkedList的插入效率比ArrayList的要高，因为LinkedList是基于链表的，插入元素时只要改变一下指针指向的位置就可以了。
要说得出这样的结论有错吗？说实在的，这样考虑没有错，但是当我们把插入这个步骤在一次细分，插入=定位+添加元素，现在我想你已经觉得上边得出的结论考虑不全面了吧。
ArrayList 定位快 添加元素需要以后之后的数据
LinkedList 定位慢 添加元素只需更改前后指定位置
现在你还有比较两个快慢的依据吗？
这时候我们就要考虑影响定位和添加的共同因素--插入的位置
当我们向第一位插入时，我们的定位基本相同，由于ArrayList需要移动之后的所有数据，所以相对就慢了很多。
前边插入
package j2ee.collection;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* ArrayList和LinkedList插入数据对比
* @author lxh96
*
*/
public class TestCollection6 {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
System.out.println("向arrayList中插入100000条数据");
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(0,i);
}
long endTime = System.currentTimeMillis();
System.out.println("ArrayList用时"+(endTime-startTime)+"ms");
System.out.println("向LinkedList中插入100000条数据");
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.add(0,i);
}
endTime = System.currentTimeMillis();
System.out.println("LinkedList用时"+(endTime-startTime)+"ms");
}
}
前边插入
中间插入
package j2ee.collection;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* ArrayList和LinkedList插入数据对比
* @author lxh96
*
*/
public class TestCollection6 {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
System.out.println("向arrayList中插入100000条数据");
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(arrayList.size()/2,i);
}
long endTime = System.currentTimeMillis();
System.out.println("ArrayList用时"+(endTime-startTime)+"ms");
System.out.println("向LinkedList中插入100000条数据");
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.add(linkedList.size()/2,i);
}
endTime = System.currentTimeMillis();
System.out.println("LinkedList用时"+(endTime-startTime)+"ms");
}
}
中间插入
最后插入
package j2ee.collection;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* ArrayList和LinkedList插入数据对比
* @author lxh96
*
*/
public class TestCollection6 {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
System.out.println("向arrayList中插入100000条数据");
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("ArrayList用时"+(endTime-startTime)+"ms");
System.out.println("向LinkedList中插入100000条数据");
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
endTime = System.currentTimeMillis();
System.out.println("LinkedList用时"+(endTime-startTime)+"ms");
}
}
最后插入
总结
如下所示
- 从集合头部添加：ArrayList慢于LinkedList
- 从集合中部添加：ArrayList快于LinkedList
- 从集合尾部添加：ArrayList慢于LinkedList
对于在最后的插入快慢保持怀疑态度，按理说应该是相差无几的，毕竟定位快慢相差无几，插入后均不需要操作其他数据。所以会有ArrayList快于LinkedList或者ArrayList慢于LinkedList的两种结果，有知道原因的望指出。
网友评论