java_集合体系之List体系总结、应用场景――07 - JAVA

(); /** * 测试插入方法（每次都将新增加的元素插入到集合开始处）、注意不要写成 add(Object o)方法、具体原因自己分析 */ private static void testInsert(){ testInsert(arrayList); testInsert(vector); testInsert(stack); testInsert(linkedList); } /** * 测试随机访问效率 */ private static void testRandomAccess(){ testRandomAccess(arrayList); testRandomAccess(vector); testRandomAccess(stack); testRandomAccess(linkedList); } /** * 测试Iterator迭代效率 */ private static void testIterator(){ testIterator(arrayList); testIterator(vector); testIterator(stack); testIterator(linkedList); } /** * 测试删除效率 */ private static void testDelete(){ testDelete(arrayList); testDelete(vector); testDelete(stack); testDelete(linkedList); } private static void testInsert(List list){ long start = currentTime(); for (int i = 0; i < 10000; i++) { list.add(0,"a"); } long end = currentTime(); System.out.println("the add method of " + list.getClass().getName() + " use time : " + (end - start) + "ms"); } private static void testRandomAccess(List list){ long start = currentTime(); for (int i = 0; i < list.size(); i++) { list.get(i); } long end = currentTime(); System.out.println("the random access method of " + list.getClass().getName() + " use time : " + (end - start) + "ms"); } private static void testIterator(List list){ long start = currentTime(); Iterator it = list.iterator(); while(it.hasNext()){ it.next(); } long end = currentTime(); System.out.println("the iterator method of " + list.getClass().getName() + " use time : " + (end - start) + "ms"); } private static void testDelete(List list){ long start = currentTime(); for (int i = 0; i < 10000; i++) { if(!list.isEmpty()){ list.remove(0); } } long end = currentTime(); System.out.println("the delete method of " + list.getClass().getName() + " use time : " + (end - start) + "ms"); } private static long currentTime(){ return System.currentTimeMillis(); } public static void main(String[] args) { testInsert(); System.out.println("=========================================================="); testRandomAccess(); System.out.println("=========================================================="); testIterator(); System.out.println("=========================================================="); testDelete(); } }

运行结果：

the add method of java.util.ArrayList use time : 32ms
the add method of java.util.Vector use time : 47ms
the add method of java.util.Stack use time : 31ms
the add method of java.util.LinkedList use time : 15ms
==========================================================
the random access method of java.util.ArrayList use time : 15ms
the random access method of java.util.Vector use time : 16ms
the random access method of java.util.Stack use time : 17ms
the random access method of java.util.LinkedList use time : 47ms
==========================================================
the iterator method of java.util.ArrayList use time : 16ms
the iterator method of java.util.Vector use time : 15ms
the iterator method of java.util.Stack use time : 17ms
the iterator method of java.util.LinkedList use time : 16ms
==========================================================
the delete method of java.util.ArrayList use time : 47ms
the delete method of java.util.Vector use time : 31ms
the delete method of java.util.Stack use time : 32ms
the delete method of java.util.LinkedList use time : 15ms

不同的运行环境、差异可能比较大。

3、差异原因分析：

在这里不会主要讨论所有的差异、而是通过源码的方式分析LinkedList与Arraylist、ArrayList与Vector在随机访问、插入、删除元素方面的差异原因、至于迭代Iterator、他们都是用从AbstractList继承的获取Iterator方法、差异不大、不再比较。

ArrayList与LinkedList

a）ArrayList的随机访问效率高于LinkedList：

随机访问是通过索引去查找元素的、LinkedList关于获取指定索引处值的源码：

/** 获取index处的元素*/
    public E get(int index) {
        return entry(index).element;
    }
    /**  获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/
    private Entry
  
    entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
        Entry
   
     e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }

关于获取指定索引处的值的源码：

    /** 检测下标是否越界*/
    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }
    /** 获取ArrayList中索引为index位置的元素*/
    public E get(int index) {
    	RangeCheck(index);

    	return (E) elementData[index];
    }

对比两者源码可以看出、LinkedList获取指定索引处的值是通过二分法先确定索引所在范围之后、在逐个查找、直到找到指定索引处、并且对每个索引都是如此、相比于ArrayList直接定位到index处的值来讲、无疑是非常浪费时间、消耗资源的、

b）ArrayList的插入、删除操作效率低于LinkedList的原因：

对于指定in

java_集合体系之List体系总结、应用场景――07(二)

3、差异原因分析：