public interface Collection<AnyType> extends Iterable<AnyType> {
	int size();
	boolean isEmpty();
	void clear();
	boolean contains(AnyType x);
	boolean add(AnyType x);
	boolean remove(AnyType x);
	java.util.Iterator<AnyType> iterator();
}

函数的功能基本上可以通过英文名看出。
Collection接口扩展了Iterable接口。实现Iterable接口的那些类可以拥有增强的for循环，该循环用于这些类之上来观察他们所有的项。

Iterator接口

实现Iterable接口的集合必须提供一个iterator的方法。

public interface Iterator<AnyType> {
	boolean hasNext();
	AnyType next();
	void remove();
}

思路：
通过iterator方法，每个集合均可创建并返回给客户一个实现Iterator接口的对象，并将当前为止的概念在对象内部存储下来。

每次调用next都会返回集合的下一项。
hasNext用来告诉是否存在下一项。
删除有next最新返回的项。

当编译器见到一个正在用于Iterable的对象的增强的for循环的时候，他用对iterator方法的那些调用代替增强的for循环以得到一个Iterator对象，然后调用next和hasNext。
注意：当使用Iterator（而不是通过一个增强的for循环间接使用）时，重要的是记住一个基本法则：如果对正在被迭代的集合进行结构上的改变（add、remove、clear）那么迭代器就不再合法（抛出异常）。如果迭代器用了自己的remove方法，那么这个迭代器依旧合法。

List接口、ArrayList、LinkedList类

先看看表(List)，除了Collection接口外，还需要一些其他方法：

public interface List<AnyType> extends Collection<AnyType> {
	AnyType get(int idx);
	AnyType set(int idx, AnyType newVal);
	void add(int idx, AnyType x);
	void remove(int idx);

	ListIterator<AnyType> listIterator(int pos);
}

说明：

1.get和set使得用户可以通过索引idx获取或修改表中的值。
2.List接口指定ListIterator方法，他返回一个更复杂的迭代器。

ArrayList 和 LinkedList

ArrayList：提供了一种可增长数组的实现。优点在于对get、set的调用花费常数时间；缺点则是在新增和删除时花费代价较高，除非变动是在末端。
LinkedList：提供了双链表的实现。优点在于对新增和删除的开销很小（变动项的位置是已知的）；缺点则是不容易做索引，对get的调用是昂贵的，除非非常接近端点位置。

简单示例：

public static void makeList1(List<Integer> lst, int N) {
	lst.clear();
	for(int i=0; i<N; i++)
		lst.add(i);
}

不管是ArrayList还是LinkedList，都是运行O(N)。因为每次调用都是在末端进行（忽略ArrayList的扩展问题a）,因此添加的花费时间为常数时间。

public static void makeList2(List<Integer> lst, int N) {
	lst.clear();
	for(int i=0; i<N; i++)
		lst.add(0, i);
}

它对于LinkedList的运行时间是O(N)，但是对于ArrayList的运行时间则是O(N^2)，因为在ArrayList中，在前端进行添加数据是一个O(N)的操作。

public static int sum(List<Integer> lst) {
	int total = 0;
	for(int i=0; i<N; i++)
		total += lst.get(i);
}

这里对于ArrayList的运行时间是O(N)，但是对于LinkedList运行时间则是O(N^2)，因为他在对get的调用时间为一个O(N)。但是要是使用一个增强的for循环，那么他对任何list的运行都是O(N)，因为迭代器将有效的从一项到下一项进行推进。

示例：删除所有的偶数项
在一个数组中，如：6、5、1、4、2。删除所有的偶数，结果为5、1.
在使用ArryaList是一个失败的策略。因为ArrayList也和一个地方删除都是低效率的。而LinkedList则会暴露两个问题，get的效率不高，remove同样低效，因为到达位置i的代价是昂贵的。

public static void removeEvensVer1(List<Integer> lst) {
	int i = 0;
	while(i < lst.size())
		if (lst.get(i)%2 == 0)
			lst.remove(i);
		else
			i++;
}

因此上面的代码对这两个List使用都是低效率的。

而下面则是通过迭代器来一步步遍历该表。这里并不是使用get获取，而是使用一个迭代器遍历，获取了高效率，但是在使用remove方式的对象是Collection的接口，因此该操作依旧是低效率的。最后需要注意的该程序会发生异常，因为在增强for循环中使用list.remove会导致迭代器非法。

public static void removeEvensVer2(List<Integer> lst) {
	for(Integer x: lst)
		if (x % 2 == 0)
			lst.remove(x);
}

最后则是使用iterator正确的方式：

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

看到对于LinkedList中，由于对迭代器的remove方法调用只是花费常数时间，因此对于LinkedList整个函数花费时间是线性的；而对于ArrayList，即使使用迭代器删除节点，但是remove后必须对数组项进行移动，因此仍然花费二次时间。

关于ListIterator接口

之前说该接口扩展了List的Iterator的功能。

public interface ListIterator<AnyType> extends Iterator<AnyType> {
	boolean hasPrevious();
	AnyType previous();
	void add(AnyType x);
	void set(AnyType newVal);
}

1.previous 和 hasPrevious 可以从表后向前进行遍历。
2.add方法，将一个新的项以当前位置放入表中。同remove一样，他也是通过迭代器看作相对位置。这一功能对ArrayList更有帮助。
3.set方法，改变被迭代器看到的值，这一功能对LinkedList更具有优势。

ArrayList类的实现

主要通过实际设计一个MyArrayList，更能看清ArrayList中代码设计的思考点。显概括主要的细节：

1.MyArrayList将保持基础数组，数组的容量，以及存储在MyArrayList中的当前项数。
2.MyArrayList将提供一种机制以改变基础数组的容量。
3.MyArrayList将提供get和set的实现。
4.MyArrayList将提供基本的例程，如size、isEmpyt、clear、remove、add等。
5.MyArrayList将提供一个实现Iterator接口的类。这个类将存储迭代序列中的下一项的下标，提供next、hasNext、remove等方法。MyArrayList的迭代器方法直接返回实现Iterator接口的该类的新构造的实例。

基本类

public classs MyArrayList<AnyType> implements Iterable<AnyType> {
	private static final int DEFAULT_CAPACITY = 10;
	private int theSize;
	private AnyType[] theItems;

	public MyArrayList()
	{ doClear(); }

	public void clear()
	{ doClear(); }

	private void doClear()
	{ theSize = 0; ensureCapacity(DEFAULT_CAPACITY); }

	public int size()
	{ return theSize; }
	public boolean isEmpty()
	{ return size() == 0; }
	public void trimToSize()
	{ ensureCapacity(size()); }

	public AnyType get(int idx) {
		if (idx < 0 || idx >= size())
			throw...
		return theItems[idx];
	}

	public AnyType set(int idx, AnyType newVal) {
		if (idx < 0 || idx >= size())
			throw...
		AnyType old = theItems[idx];
		theItems[idx] = newVal;
		return old;
	}

	public void ensureCapacity(int newCapacity) {
		if (newCapacity < theSize)
			return;
		AnyType[] old = theItems;
		theItems = (AnyType[]) new Object[newCapacity];
		for(int i=0; i<size(); i++)
			theItems[i] = old[i];
	}

	public boolean add(AnyType x) {
		add(size(), x);
		return true;
	}

	public void add(int idx, AnyType x) {
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		for (int i = theSize; i>idx; i--)
			theItems[i] = theItems[i-1];
		theItems[idx] = x;
		theSize++;
	}

	public AnyType remove(int idx) {
		AnyType removedItem = theItems[idx];
		for(int i = idx; i<size() - 1; i++)
			theItems[i] = theItems[i + 1];
		theSize--;
		return removedItem;
	}

	public java.util.Iterator<AnyType> iterator() 
	{return new ArrayListIterator();}

	private class ArrayListIterator implements java.util.Iterator<AnyType> {
		private int current = 0;
		public boolean hasNext()
		{ return current < size(); }

		public AnyType next() {
			if (!hasNext())
				throw ...
			return theItems[current++];
		}
		
		public void remove()
		{ MyArrayList.this.remove(--current); }
	}
}

LinkedList类的实现

通过设计一个MyLinkedList的实现。作为双链表的方式来实现，还需要保留两端的引用。

1.MyLinkedList类本身，包含到两端的链、表的大小及一些方法。
2.Node类，一个节点包含数据以及前一个节点和后一个节点。
3.LinkedListIterator类，该类抽象类位置的概念。提供了next、hasNext、remove等方法。
4.添加头节点和尾节点，这些是标记节点，可以通过排除许多特殊情形极大的简化了编码。

public class MyLinkedList<AnyType> implements Iterable<AnyType> {
	private static class Node<AnyType> {
		public Node(AnyType d, Node<AnyType> p, Node<AnyType> n)
			{ data=d; prev=p; next=n; }

		public AnyType data;
		public Node<AnyType> prev;
		public Node<AnyType> next;
	}
	
	public MyLinkedList()
		{ doClear(); }

	public void clear()
		{ doClear() }
	public int size()
		{ return theSize; }
	public boolean isEmpty()
		{ return size()==0; }
	
	public boolean add(AnyType x)
		{ add(size(), x); return true }
	public void add(int idx, AnyType x)
		{ addBefore(getNode(idx, 0, size()), x); }
	public AnyType get(int idx)
		{ return getNode(idx).data; }
	public AnyType set(int idx, AnyType newVal) {
		Node<AnyType> p = getNode(idx);
		AnyType oldVal = p.data;
		p.data = newVal;
		return oldVal;
	}
	public AnyType remove(int idx)
		{ return remove(getNode(idx)); }
	
	private void addBefore(Node<AnyType> p, AnyType x)

private void addBefore(Node<AnyType> p, AnyType xp)
}