三、表 栈和队列之Java Collections

Java Collections API
1.Collection接口
    Collection扩展了Iterable接口。
2.Iterator接口
    实现Iterable接口的Collection必须提供一个称为iterator的方法，该方法返回一个Iterator类型的对象。Iterator接口的目的在于：通过iterator方法，每个Collection都可以创建并返回一个实现Iterator接口的对象，并将当前位置在对象内部保存下来。例如，每次调用next(),都返回Collection的下一项，hasNext()用来返回是否存在下一项。
    Iterator适用于对Collection做简单遍历。Iterator的remove()可以删除next()返回的项，而要继续使用remove()必须再次调用next()。优于Collection的remove(),Iterator的remove()在于不必像前者一样先找出被删除的项，减少了开销。
    直接使用Iterator时需注意，如果对集合进行了add(),remove(),clear()等改变了数据结构的方法，再使用Iterator就用出现异常。这意味着，只有在需要立即使用迭代器的时候，才应该获取迭代器。
3.List、ArrayList和LinkedList
    List接口继承了Collection接口，并增加了一些其他方法，如get(),set(),size(),remove()等(常用方法，不多赘述)。
    List常用的实现方式有ArrayList和LinkedList。
    ArrayList类提供了一种List的可增长的数组实现。优点是：get(),set()方法时间复杂度为常数级，缺点是：插入和删除的花销较大（除非是在队尾进行）。ArrayList有其容量，表示基础数组的大小。需要时将自动增加其容量。
    LinkedList类提供了List的双链表实现。优点是：在表的前端进行添加和删除时间复杂度为常数级，缺点是：不容易作索引（除非很接近表的端点）。
    对搜索而言，ArrayList和LinkedList都是低效的。
4.remove()对LinkedList类的使用
例子：将List中所有的值为偶数的项删除。
    ArrayList的remove()花销过大，因此采用LinkedList。
    思路1：for循环内，先用get()获取值，判断是否为偶数，是则remove()。分析：get()花销较大，而且remove要找到第i个元素依旧有开销。
    思路2：用迭代器一步步遍历表，然后用collection的remove()删除偶数。分析：迭代器遍历是高效的，而collection的remove()不仅需要再次搜索该项造成效率低下，而且会产生异常。
    思路3：构造一个Iterator对象，当找到偶数值项后，用迭代器来删除刚看到的值。分析：对LinkedList来说，该迭代器的remove方法调用花费为常数时间，因为该迭代器位于需要被删除的节点。不过对于ArrayList来说，即使迭代器位于需要被删除的节点，其remove()仍花费较大。
    思路3的代码如下：

	public static void remove(List<Integer> list){
		Iterator<Integer> ite=list.iterator();
		while(ite.hasNext()){
			if(ite.next()%2==0)
				ite.remove();
		}
	}
}