Java集合与循环：主要对比ArrayList和LinkedList

 

一般大家都知道ArrayList和LinkedList的大致区别：

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

     2.对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要从前到后移动指针。

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

 其实，Linkedlist相较于Arraylist的唯一优势在于集合前段部分的数据的插入，中后段的数据插入效率依然不如ArrayList。

 

Java中，对于集合的循环常见形式有：下标For循环、ForEach循环、普通迭代循环(list.iterator())、针对List的迭代循环(list.listIterator())、以及相应的While循环。

1. 循环效率(针对数组实现的集合)

各循环效率的对比，其实要看循环的数据量的数量级，以及集合包含的单个对象的大小。

一般而言，while循环与for循环的效率上的区别并不大。

         对于线性数组集合而言，如果循环的数量级越大，下标循环的效率越高。请看以下10次执行平均值数据(ArrayList(Integer))，时间单位为nanosecond。

循环数量级	10	1000	100000	10000000
	average	average	average	average
listForLoop(下标)	5513	103490	6688946	51902989
listForEach	126454	321838	10066022	54252235
listForIterator	4562	307999	9226809	53535675
listForListIterator	117330	306592	9236961	56553463
listWhileLoop(下标)	1635	119839	5978926	54596847
listWhileIterator	4372	321078	9301785	56176724
listWhileListIterator	5703	318683	9342504	61759977

         由表格数据可以看出，下标循环的优势是显而易见的，在千万级的数据量时，反而这种差距会缩小。因为ArrayList本身就是使用数组实现的，所以用下标来取其中的元素，是一种很直接的方式，开销也小。但是下标循环和foreach循环都是不支持在循环过程中改变集合，而普通迭代与list迭代都是支持改变集合的。

         所以一般不推荐使用foreach循环，因为不仅效率低，而且循环过程中，改变集合会报异常(ConcurrentModificationException)。如果是在多线程编程中，一般减少使用下标循环，而使用foreach和迭代循环，会比较安全。

 

2. 测试过程中的循环代码如下：

a. listForLoop：

	public long listForLoop(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		for (int i = 0,len = list.size(); i < len; i++) {
			s = list.get(i);
		}
		end = System.nanoTime();
		return end-start;
	}

 

b. listForEach：

	public long listForEach(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		for (Integer i : list) {
			s = i;
		}
		end = System.nanoTime();
		return end-start;
	}

 

c. listForIterator：

	public long listForIterator(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		for (Iterator it = list.iterator(); it.hasNext();) {
			s = (Integer) it.next();
		}
		end = System.nanoTime();
		return end-start;
	}

 

d. listForListIterator：

	public long listForListIterator(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		for (Iterator it = list.listIterator(); it.hasNext();) {
			s = (Integer) it.next();
		}
		end = System.nanoTime();
		return end-start;
	}

 

e. listWhileLoop：

	public long listWhileLoop(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		int len = list.size();
		start=System.nanoTime();
		int i = 0;
		while (i<len) {
			s=list.get(i);
			i++;
		}
		end = System.nanoTime();
		return end-start;
	}

 

f.  listWhileIterator：

	public long listWhileIterator(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		Iterator it = list.iterator();
		while (it.hasNext()) {
			s=(Integer) it.next();
		}
		end = System.nanoTime();
		return end-start;
	}

 

g. listWhileListIterator：

	public long listWhileListIterator(ArrayList<Integer> list) {
		long start =0L,end=0L;
		@SuppressWarnings("unused")
		Integer s = null;
		start=System.nanoTime();
		Iterator it = list.listIterator();
		while (it.hasNext()) {
			s=(Integer) it.next();
		}
		end = System.nanoTime();
		return end-start;
	}

 

 

3. 具体list.iterator()与list.listIterator(迭代的区别如下：

a、ListIterator有add()方法，可以向List中添加对象，而Iterator不能。

b、ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历。但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。

c、ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator 没有此功能。

d、都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改对象的引用。

 

 

评论

1 楼 zendly 2016-03-04