Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

java 集合系列目录:

Java 集合系列 01 总体框架

Java 集合系列 02 Collection架构

Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例

Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例 

Java 集合系列 05 Vector详细介绍(源码解析)和使用示例

Java 集合系列 06 Stack详细介绍(源码解析)和使用示例

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

 

第1部分 List概括

先回顾一下List的框架图

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

(01) List 是一个接口,它继承于Collection的接口。它代表着有序的队列。
(02) AbstractList 是一个抽象类,它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。
(03) AbstractSequentialList 是一个抽象类,它继承于AbstractList。AbstractSequentialList 实现了“链表中,根据index索引值操作链表的全部函数”。

(04) ArrayList, LinkedList, Vector, Stack是List的4个实现类。
  ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低。
  LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率低。
  Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。
  Stack 是栈,它继承于Vector。它的特性是:先进后出(FILO, First In Last Out)。

 

第2部分 List使用场景

下面先概括的说明一下各个List的使用场景后面再分析原因

如果涉及到“栈”、“队列”、“链表”等操作,应该考虑用List,具体的选择哪个List,根据下面的标准来取舍。
(01) 对于需要快速插入,删除元素,应该使用LinkedList。
(02) 对于需要快速随机访问元素,应该使用ArrayList。
(03) 对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。
       对于“多线程环境,且List可能同时被多个线程操作”,此时,应该使用同步的类(如Vector)。


通过下面的测试程序,我们来验证上面的(01)和(02)结论。参考代码如下:

 

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)
  1 /**
  2  * 对比ArrayList和LinkedList的插入、随机读取效率、删除的效率
  3  * 
  4  * @ClassName: List_test_1
  5  * @author Xingle
  6  * @date 2014-5-29 下午5:25:11
  7  */
  8 public class List_test_1 {
  9     private static int COUNT_ = 100000;
 10 
 11     private static LinkedList<Integer> linkedList = new LinkedList<Integer>();
 12     private static ArrayList<Integer> arraylist = new ArrayList<Integer>();
 13     private static Vector<Integer> vector = new Vector<Integer>();
 14     private static Stack<Integer> stack = new Stack<Integer>();
 15 
 16     public static void main(String[] args) {
 17         // 插入
 18         insertByPosition(stack);
 19         insertByPosition(linkedList);
 20         insertByPosition(arraylist);
 21         insertByPosition(vector);
 22         
 23 
 24         // 读取
 25         readByPosition(stack);
 26         readByPosition(linkedList);
 27         readByPosition(arraylist);
 28         readByPosition(vector);
 29         
 30 
 31         // 删除
 32         deleteByPosition(stack);
 33         deleteByPosition(linkedList);
 34         deleteByPosition(arraylist);
 35         deleteByPosition(vector);
 36         
 37 
 38     }
 39 
 40     /**
 41      * 从list的指定位置删除COUNT个元素,并统计时间
 42      * 
 43      * @author xingle
 44      * @data 2014-5-29 下午5:33:55
 45      */
 46     private static void deleteByPosition(List<Integer> list) {
 47         long start = getCurrentTime();
 48         for (int i = 0; i < COUNT_; i++) {
 49             list.remove(0);
 50         }
 51         long end = getCurrentTime();
 52         long interval = end - start;
 53         System.out.println(getListName(list) + " : delete " + COUNT_
 54                 + " delete "+COUNT_+" elements from the 1st position use time:" + interval
 55                 + " ms");
 56 
 57     }
 58 
 59     /**
 60      * 根据position,从list中读取元素,并统计时间
 61      * 
 62      * @param list
 63      * @author xingle
 64      * @data 2014-5-29 下午5:32:58
 65      */
 66     private static void readByPosition(List<Integer> list) {
 67         long start = getCurrentTime();
 68         for (int i = 0; i < COUNT_; i++) {
 69             list.get(i);
 70         }
 71         long end = getCurrentTime();
 72         long interval = end - start;
 73         System.out.println(getListName(list) + " : read " + COUNT_
 74                 + " elements by position use time:" + interval
 75                 + " ms");
 76 
 77     }
 78 
 79     /**
 80      * 向list的指定位置插入COUNT个元素,并统计时间
 81      * 
 82      * @param list
 83      * @author xingle
 84      * @data 2014-5-29 下午5:32:16
 85      */
 86     private static void insertByPosition(List<Integer> list) {
 87         long start = getCurrentTime();
 88         for (int i = 0; i < COUNT_; i++) {
 89             list.add(0, i);
 90         }
 91         long end = getCurrentTime();
 92         long interval = end - start;
 93         System.out.println(getListName(list) + " : insert " + COUNT_
 94                 + " elements into the 1st position use time:" + interval
 95                 + " ms");
 96     }
 97 
 98     /**
 99      * 获取list名称
100      * 
101      * @return
102      * @author xingle
103      * @data 2014-5-29 下午5:38:02
104      */
105     private static String getListName(List<Integer> list) {
106         if (list instanceof LinkedList)
107             return "LinkedList";
108         else if (list instanceof ArrayList)
109             return "ArrayList";
110         else if (list instanceof Stack)
111             return "Stack";
112         else if(list instanceof Vector)
113             return "Vector";
114         else 
115             return "List";
116     }
117 
118     /**
119      * 获取当前时间
120      * 
121      * @return
122      * @author xingle
123      * @data 2014-5-29 下午5:35:33
124      */
125     private static long getCurrentTime() {
126         return System.currentTimeMillis();
127     }
128 
129 }
Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

 执行结果:

Stack : insert 100000 elements into the 1st position use time:1724 ms
LinkedList : insert 100000 elements into the 1st position use time:31 ms
ArrayList : insert 100000 elements into the 1st position use time:1724 ms
Vector : insert 100000 elements into the 1st position use time:1651 ms
Stack : read 100000 elements by position use time:9 ms
LinkedList : read 100000 elements by position use time:8969 ms
ArrayList : read 100000 elements by position use time:10 ms
Vector : read 100000 elements by position use time:10 ms
Stack : delete 100000 delete 100000 elements from the 1st position use time:2674 ms
LinkedList : delete 100000 delete 100000 elements from the 1st position use time:23 ms
ArrayList : delete 100000 delete 100000 elements from the 1st position use time:2757 ms
Vector : delete 100000 delete 100000 elements from the 1st position use time:2087 ms

 

从中,我们可以发现
插入10万个元素,LinkedList所花时间最短:31ms
删除10万个元素,LinkedList所花时间最短:23ms
遍历10万个元素,LinkedList所花时间最长:8969 ms;而ArrayList、Stack和Vector则相差不多,都只用了几秒。

考虑到Vector是支持同步的,而Stack又是继承于Vector的;因此,得出结论:
(01) 对于需要快速插入,删除元素,应该使用LinkedList。
(02) 对于需要快速随机访问元素,应该使用ArrayList。
(03) 对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类。

 

第3部分 LinkedList和ArrayList性能差异分析

下面我们看看为什么LinkedList中插入元素很快,而ArrayList中插入元素很慢

LinkedList.java中向指定位置插入元素的代码如下

 

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)
/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

 /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

 

 

ensureCapacity(size+1) 的作用是“确认ArrayList的容量,若容量不够,则增加容量。
真正耗时的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);

Sun JDK包的java/lang/System.java中的arraycopy()声明如下:

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

arraycopy()是个JNI函数,它是在JVM中实现的。sunJDK中看不到源码,不过可以在OpenJDK包中看到的源码。网上有对arraycopy()的分析说明,请参考:System.arraycopy源码分析 
实际上,System.arraycopy(elementData, index, elementData, index + 1, size - index); 会移动index之后所有元素即可这就意味着,ArrayList的add(int index, E element)函数,会引起index之后所有元素的改变!


通过上面的分析,我们就能理解为什么LinkedList中插入元素很快,而ArrayList中插入元素很慢。
“删除元素”与“插入元素”的原理类似,这里就不再过多说明。

 

接下来,我们看看 “为什么LinkedList中随机访问很慢,而ArrayList中随机访问很快”

先看看LinkedList随机访问的代码

 


 

转载:http://www.cnblogs.com/skywang12345/p/3308900.html

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析),布布扣,bubuko.com

Java 集合系列 07 List总结(LinkedList, ArrayList等使用场景和性能分析)

上一篇:关于指向指针的指针


下一篇:NC70 单链表的排序