刚看完《数据结构与算法分析java语言描述》的第3章中的表，下面回忆下主要知识点，主要说明各列表之间的关系，以及各自的优缺点。其中牵涉到内部类和嵌套类。
1 Collection API
public interface Collection<AnyType> extens Iterable<AnyType>
{
int size();
boolean isEmpty();
void clear();
boolean contains(AnyType x);
boolean add(AnyType x);
boolean remove(AnyType x);
java.util.Iterator<AnyType> iteratoe();
}
2 Iterator API
public interface Iterator<AnyType>
{
boolean hasNext();
AnyType next();
void move();
}
3 List
public interface List<AnyType> extents 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);
}
4 ListIterator
public interface ListIterator<AnyType> extents Iterator<AnyType>
{
boolean hasPrevious();
AnyType previous();
void add(AnyType x);
void set(AnyType newVal);
}
5 ArrayList是List的一种可增长的数组实现，优点是get和set花费常数时间，而insert和remove代价昂贵。除非是在末端进行。
6 LinkedList是List的双链表实现，优点是insert和remove开销较小，而get和set花费较大。不容易操作索引。
7 iterator的remove方法比LinkedList效率更高，因为迭代器位于需要被删除的节点附近。但是使用iterato时，list的结构不能被改变（例如insert，remove等）。
8 嵌套内常常用static放在类内部，其无法确定引用的主体；而内部类无需static声明，并且可自动确定引用的主体为其外部类。