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

谁践踏了优雅 2023-06-04 02:45 18阅读 0赞

# [Java数据结构之LinkedList、ArrayList的效率分析][Java_LinkedList_ArrayList] #

### 前言： ###

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

### 先了解一下List      ###

`  List列表类，顺序存储任何对象（顺序不变），可重复。`

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

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

L`ist基本操作`

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

### ArrayList、LinkedList性能对比 ###

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

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

![复制代码][copycode.gif]

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));
    
        }

![复制代码][copycode.gif]

测试LinkedList函数

![复制代码][copycode.gif]

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));
    
        }

![复制代码][copycode.gif]

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

![950883-20170306162755781-2130411166.png][]

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

*  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效率问题，有助于在以后的开发中根据实际场景选择合适的技术方案。

干我们这行，啥时候懈怠，就意味着长进的停止，长进的停止就意味着被淘汰，只能往前冲，直到凤凰涅槃的一天！

转载于:https://www.cnblogs.com/think90/p/11443181.html

[Java_LinkedList_ArrayList]: https://www.cnblogs.com/whoislcj/p/6508851.html
[copycode.gif]: /images/20230601/3d4c6af67bb64ae79bc0570358115841.png
[950883-20170306162755781-2130411166.png]: /images/20230601/499f6a57bece4e1396700e9afe708ee6.png