LinkedList的Iterator的性能分析

69 阅读 0 评论 46 点赞

我是靠谱客的博主温婉泥猴桃，最近开发中收集的这篇文章主要介绍LinkedList的Iterator的性能分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

LinkedList的Iterator 的性能颈瓶：
对于Iterator 的next每次都会返回一个LinkedList的内部类return new ListItr(index),然后调用这个内部类的next方法。
而ListItr(index)每次初始化时都时从头指针开始从新定位的，所以对于海量数据的遍历时，性能是非常糟糕的，尽管其做了折半的查找优化。
ListItr的初始化代码如下：

ListItr(int index) {
	    if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index+
						    ", Size: "+size);
	    if (index < (size >> 1)) {
		next = header.next;
		for (nextIndex=0; nextIndex<index; nextIndex++)
		    next = next.next;
	    } else {
		next = header;
		for (nextIndex=size; nextIndex>index; nextIndex--)
		    next = next.previous;
	    }
	}

这个LinkedList作者是Josh Bloch，版本是version 1.61, 02/19/04，不知道之后的版本是否做了改进。