Java数据结构之LinkedList、ArrayList的效率分析

时间:2022-12-22 10:17:59

前言:

     在我们平常开发中难免会用到List集合来存储数据,一般都会选择ArrayList和LinkedList,以前只是大致知道ArrayList查询效率高LinkedList插入删除效率高,今天来实测一下。

先了解一下List     

  List列表类,顺序存储任何对象(顺序不变),可重复。

  List是继承于Collection的接口,不能实例化。实例化可以用:

  • ArrayList(实现动态数组),查询快(随意访问或顺序访问),增删慢。整体清空快,线程不同步(非线程安全)。数组长度是可变的百分之五十延长
  • LinkedList(实现链表),查询慢,增删快。
  • Vector(实现动态数组),都慢,被ArrayList替代。长度任意延长。线程安全(同步的类,函数都是synchronized)
  • Stack(实现堆栈)继承于Vector,先进后出。

    List基本操作

  • 插入:add()
  • 查找:get()
  • 删除:remove(int index)
  • 修改:set()
  • 清空表:clear()
  • 遍历:用Iterator迭代器遍历每个元素

ArrayList、LinkedList性能对比

为了很好的对比效率,直接写个测试程序看下运行结果

模拟5w条数据指定插入第一位,然后查询全部,循环删除第一位,下面是测试ArrayList函数

private void testArrayList(){
ArrayList
<String> list=new ArrayList<>();
int maxTestCount=50000;

//测试添加
long start =System.currentTimeMillis();

for(int i =0;i<maxTestCount;i++){
list.add(
0,String.valueOf(i));
}

long end =System.currentTimeMillis();

Log.e(TAG,
"ArrayList add cost time :"+(end-start));

//测试查询
start =System.currentTimeMillis();

for(int i =0;i<maxTestCount;i++){
list.get(i);
}

end
=System.currentTimeMillis();

Log.e(TAG,
"ArrayList get cost time :"+(end-start));

//测试查询
start =System.currentTimeMillis();

for(int i =maxTestCount;i>0;i--){
list.remove(
0);
}

end
=System.currentTimeMillis();

Log.e(TAG,
"ArrayList remove cost time :"+(end-start));

}

测试LinkedList函数

private void testLinkedList(){
LinkedList
<String> list=new LinkedList<>();
int maxTestCount=50000;

//测试添加
long start =System.currentTimeMillis();

for(int i =0;i<maxTestCount;i++){
list.add(
0,String.valueOf(i));
}

long end =System.currentTimeMillis();

Log.e(TAG,
"LinkedList add cost time :"+(end-start));

//测试查询
start =System.currentTimeMillis();

for(int i =0;i<maxTestCount;i++){
list.get(i);
}

end
=System.currentTimeMillis();

Log.e(TAG,
"LinkedList get cost time :"+(end-start));


//测试查询
start =System.currentTimeMillis();

for(int i =maxTestCount;i>0;i--){
list.remove(
0);
}

end
=System.currentTimeMillis();

Log.e(TAG,
"LinkedList remove cost time :"+(end-start));

}

先后调用两个函数,看下运行结果

Java数据结构之LinkedList、ArrayList的效率分析

通过上面的运行结果可以大致得出以下结论:

  • ArrayList插入、删除效率明显低于LinkedList
  • ArrayList查询效率远远高于LinkedList

通过上面的结构是不是就可以认为插入删除频繁选择LinkedList,追求查询效率就选择ArrayList呢,我们先来分析一下效率差别的原因,这个就跟数据结构有关系了,可以参考一些数据结构中链表的知识,arraylist 顺序表,用数组的方式实现。想想数组要查询那个元素只给出其下标即可,所以才说arraylist随机访问多的场景比较合适。但是如果删除某个元素比如第 i 个元素,则要将 i 之后的元素都向前移一位以保证顺序表的正确,增加也是一样,要移动多个元素。要多次删除增加的话是很低效的。而LinkedList是双向链表,注意是链表。要查询只能头结点开始逐步查询,没有什么给出下标即可直接查询的便利,需要遍历。但是,如果要增加后删除一个元素的话,只需要改变其前后元素的指向即可,不需要像arraylist那样整体移动,所以才说多用于增删多的场合。

很感谢博友的建议与帮助,由于LinkedList查询只能从头结点开始逐步查询的,可以使用 iterator 的方式,就不用每次都从头结点开始访问,因为它会缓存当前结点的前后结点。实测查询效率与ArrayList没有太大差别

LinkedList<String> list = new LinkedList<>();
Iterator
<String> it = list.iterator();
while(it.hasNext()){
String s
= it.next();
}

List其他知识扩展

Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。
Stack 是栈,它继承于Vector。它的特性是:先进后出(FILO, First In Last Out)。

总结:

   通过运行结果和查阅资料基本上验证了ArrayList和LinkedList效率问题,有助于在以后的开发中根据实际场景选择合适的技术方案。