ArrayList和LinkedList的区别（代码测试）

川长思鸟来 2022-12-04 07:59 113阅读 0赞

## ArrrayList: ##

ArrayList是一个数组结构（Vector同理），数组在内存中是一片连续存在的片段，在查找元素的时候数组能够很方便的通过内存计算直接找到对应的元素内存。

## LinkedList ##

LinkedList的底层是一个双向链表结构，在进行查找操作的时候需要花费非常多的时间来遍历整个链表，但是由于其链表结构的特殊性，在插入、删除数据的时候，只需要修改链表节点的前后指针就可以完成操作。

--------------------

## 测试 ##

代码

static int size=10000000;
    
        static void arraylist(ArrayList a){ 
    
            //截取当前时间/毫秒
            long l=System.currentTimeMillis();
    
            for (int i=0;i<size;i++){ 
                a.add(i);
    
            }
            long c=System.currentTimeMillis();
    
            System.out.println("ArrayList插入元素所需时间："+(c-l)+"ms");
            
            long g=System.currentTimeMillis();
    
            for (int i=0;i<100000;i++){ 
                a.get(i);
            }
            long g1=System.currentTimeMillis();
            System.out.println("ArrayList查找元素所需时间："+(g1-g)+"ms");
            
            long l2=System.currentTimeMillis();
    
            int j=500;
            for (int i=0;i<j;j--){ 
                a.remove(i);
            }
    
            long c2=System.currentTimeMillis();
    
            System.out.println("ArrayList删除元素所需时间："+(c2-l2)+"ms");
        }
    
        static void linklist(LinkedList b){ 
            long l=System.currentTimeMillis();
    
            for (int i=0;i<size;i++){ 
                b.add(i);
            }
    
            long c=System.currentTimeMillis();
    
            System.out.println("LinkedList插入元素所需时间："+(c-l)+"ms");
    
            long g=System.currentTimeMillis();
            for (int i=0;i<10000;i++){ 
                b.get(i);
            }
    
            long g1=System.currentTimeMillis();
            System.out.println("LinkedList插入查找元素所需时间："+(g1-g)+"ms");
    
            long l1=System.currentTimeMillis();
    
            for (int i=size-1;i>-1;i--){ 
                b.remove(i);
            }
            long c1=System.currentTimeMillis();
    
            System.out.println("LinkedList删除元素所需时间："+(c1-l1)+"ms");
        }
        public static void main(String[] args) { 
    
            ArrayList a=new ArrayList();
            LinkedList b=new LinkedList();
            arraylist(a);
            linklist(b);
        }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDgzMDA5_size_16_color_FFFFFF_t_70_pic_center]  
ArrayList插入或删除数据时，需要搬运其他数据，也就是修改它们的下标，其效率远不如LinkedList。我的测试代码中仅仅删除了500个数据，其时间就不少了。但ArrayList可以直接通过内存序号下标来访问，查找的效率高远比LinkedList高。

LinkedList查找元素需要遍历链表查找，效率不如ArrayList，在插入、删除操作的时候可以直接修改链表节点的前后指针节点，效率远高于ArrayList。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDgzMDA5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/fa591f512ffc47a0b124fe8cbaa68973.png