深入理解ArrayList 和 LinkedList 区别

ArrayList的内部实现是基于数组，因此，它使用get方法访问列表中的任意一个元素时，它的速度要比LinkedList快。LinkedList的内部实现是基于链表的，LinkedList中的get方法是按顺序从列表的一端到另一端。对LinkedList而言，只有这种查找方法。

Bruca Eckel描述如下：

Java编程思想对List的描述（4版P233）：

基本的ArrayList，它长于随机访问，但是在List的中间插入和一处速度较慢。

LinkedList，它通过代价较低的在List中间进行插入和删除操作，提供了优化的顺序访问，LinkedList在随机访问方面相对较慢，但是它的特性较ArrayList更大。

---

实现分析：

• 问题：假设一个很大的列表，其中元素已经排序（在静态代码块中实现），这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较ArrayList和LinkedList时的查询速度。然后在比较插入/删除的速度。
• 测试结果
  N=1000时，在前段1/10,1/5处两者几乎无差别，可忽略。
  N=10000时，在前段1/5处或更前面的位置，LinkedList的效率更高，
  N=100000时，在前段1/10处或更前面的位置，LinkedList的效率更高

---

代码如下，第一，保证ArrayList和Linked先被创建出来，排除ArratList自动扩容的问题。

package demo;

import java.util.ArrayList;  
import java.util.Arrays;
import java.util.Collections;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.Random;

public class Test3 {  

    public static final int N = 100000;   
    public static List values;   

    //保证在静态代码块中先生成List，排除扩容问题
    static{   
        Integer vals[] = new Integer[N];   
        Random r = new Random();   

        for(int i=0 ,currval = 0;i < N;i++){ 
         //Integer数组  vals[]的每一个元素 初始化都为0
            vals[i] = new Integer(currval);  
            currval += r.nextInt(100) + 1;  //currval=currval+r.nextInt(100)+1; 
        }   
        //数组生成集合List
        values = Arrays.asList(vals);   
    }

    static long getTime(List lst){   
        long start = System.currentTimeMillis();   //当前时间
        for(int i=0;i<N;i++){   
            int index = Collections.binarySearch(lst, values.get(i));   //二分法
            if(index!=i) 
             System.out.println("***错误***");   
        }   

        return System.currentTimeMillis() - start;   
    } 

    public static long insertTime(List list){  
        long time = System.currentTimeMillis();
        //控制在List插入删除的位置
        int index = N/10;
        for(int i=100;i<N;i++){  
            //在下标index出插入
            list.add(index,i);  //N=100000,1/10处之后 LinkedList就开始变慢了

            //将下标index处的删除
            list.remove(index); 
            //remove掉之前添加的对象 执行次数是（index-100）次
            if(i == index)  
                break;
        }  
        return System.currentTimeMillis()-time;  
    }  

    public static void main(String[] args) {
        System.out.println("linked time:"+getTime(new LinkedList(values)));  
        System.out.println("array time:"+getTime(new ArrayList(values)));  
        System.out.println("linked insert time:"+insertTime(new LinkedList(values))); 
        System.out.println("array insert time:"+insertTime(new ArrayList(values)));  
    }
}  

结果：
N=100000时，index=N/10时
linked time:19794
array time:10
linked insert time:334
array insert time:463
如果插入到1/10后段

结果：
N=10000时，index=N/5时
linked time:188
array time:5
linked insert time:12
array insert time:12

结果：
N=1000时，index=N/10或者index=N/5两者几乎无差别
linked time:7
array time:2
linked insert time:0
array insert time:1

---

讨论：

集合元素很多时，当需要插入数据的时候，如果是在集合的前段（大概集合容量的前1/10）处插入数据时，linkedlist性能明显（内存开销、时间）优于arraylist，但是！！！！当在集合的中部甚至靠后的位置插入大量数据时，arraylist的性能反而远远优于linkedlist，所以，linkedlist相较于arraylist的优势在于集合前段的数据的插入和内存的开销。
对于ArraList，对列表中间插入和删除LinkedList是廉价操作，但是对于ArrayList，这可是代价高昂的操作。因为对内存的开销很大，是数组复制的原因。

ArrayList源码

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }  

Arrays.copyOf()，显然在数据很大时，任然需要数组复制，必然对内存的开销增大。

---

LinkedList源码：

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

---

在LinkedList中有一个私有的内部类

private static class Entry {   
         Object element;   
         Entry next;   
         Entry previous;   
     }

• 每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。
  ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

• LinkedList是基于链表来操作的，LinkedList保存了前后元素的信息，LinkedList在随机访问方面相对较慢，但是它的特性较ArrayList更大，系统不单也要考虑速度，对内存的开销也要考虑。

---

总结

• ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：
  1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList无法进行高效的元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费是它的每一个元素都需要消耗相当的空间来保存前后元素的位置。

在一列数据(无论数据是大是少)的后面部分添加/删除数据—不是在前面或中间；或者任何时候需要访问List元素时,使用ArrayList更好；在一列数据(无论数据量很大)的前面或中间部分添加/删除数据,就应该使用LinkedList了。 总体而言，ArrayList实际开发中用的更多。