LinkedList和ArrayList有什么区别？-蒲公英云

LinkedList和ArrayList有什么区别？

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条数据时，输出结果：

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

自由性不同

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

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

主要控件开销不同

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

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

ArrayList和LinkedList的缺点

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