LinkedList和ArrayList有什么区别？

古城微笑少年丶 2024-03-23 18:32 23阅读 0赞

ArrayList和LinkedList的大致区别：

*  ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

*  对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

*  对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

#### 数据结构不同 ####

ArrayList是Array（动态数组）的数据结构。

LinkeedList是List（链表）的数据结构。

#### 效率不同 ####

当随机访问List（get 和 set操作）时，ArrayList比LinkedList效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。

当对数据进行增加和删除的操作（add 和 remove操作）时，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以进行增删操作时，会对操作之后所有数据的下标索引造成影响，需要进行数据移动。但是实际情况并非这样，对于添加或删除，LinkedList和ArrayList并不能明确说明谁快谁慢，下面通过测试程序详细分析。

import java.util.*;
    
    public class ListTest {
        static List<Integer> array=new ArrayList<Integer>();
        static List<Integer> linked=new LinkedList<Integer>();
         
         public static long getTime(List<Integer> list){
             long startTime=System.currentTimeMillis();
             for(int i = 0; i < 10000; i++){
                int index = Collections.binarySearch(list, list.get(i));
                 if(index != i){
                     System.out.println("ERROR!");
                 }
             }
             return System.currentTimeMillis()-startTime;
         }
     
         //插入数据
         public static long insertTime(List<Integer> list){
             /*
              * 插入的数据量和插入的位置是决定两者性能的主要方面，
              * 我们可以通过修改这两个数据，来测试两者的性能
              */
            long num = 10000; //表示要插入的数据量
             int index = 1000; //表示从哪个位置插入
             long startTime=System.currentTimeMillis();
             for(int i = 1; i < num; i++){
                 list.add(index, i);
             }
             return System.currentTimeMillis()-startTime;
     
         }
         
         public static void main(String[] args) {
     
             //首先分别给两者插入10000条数据
             for(int i=0;i<10000;i++){
                 array.add(i);
                 linked.add(i);
             }
             //获得两者随机访问的时间
             System.out.println("ArrayList查找元素耗时:"+getTime(array));
             System.out.println("LinkedList查找元素耗时:"+getTime(linked));
             //获得两者插入数据的时间
            System.out.println("ArrayList添加元素耗时:"+insertTime(array));
             System.out.println("LinkedList添加元素耗时::"+insertTime(linked));
     
         }
     }

在处理5000条数据时，输出结果：

![9f0085670853e0accceb652308845494.png][]

在处理10000条数据时，输出结果：

![6556abebe0a933ed051d18ccb39df571.png][]

#### 自由性不同 ####

ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建之后添加数据，通过调用下标进行使用。

LinkedList自由性较高，能够动态的随数据量的变化而变化，但不方便使用。

#### 主要控件开销不同 ####

ArrayList主要控件开销在于需要在List列表预留一定的空间。

LinkedList则在于需要存储节点信息以及节点指针信息。

### ArrayList和LinkedList的缺点 ###

1.  对ArrayList和LinkedList而言，在列表末尾增加一个元素所需要的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。
2.  在ArrayList集合中添加或者删除一个元素时，当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
3.  LinkedList集合不支持高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。
4.  ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

[9f0085670853e0accceb652308845494.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5fd8f5787ec541a2a357f9b5b17c1f68.png
[6556abebe0a933ed051d18ccb39df571.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/18af3ae7e8a64d8f9330dfc3da179986.png