在类库中，Java语言包含有一些不同数据结构的实现。该语言的这一部分通常叫作Collection API。表ADT是在Collections API中实现的数据结构之一。
一、Collection接口
Collections API位于java.util包中。（集合）collection的概念在Collection接口中得到抽象，它存储一组类型相同的对象。
Collection接口中的许多方法所做的工作由它们的英文名称就可以看出。如，size返回集合中的元素总数（集合大小）；isEmpty当集合为空时返回true……
Collection接口扩展了Iterable接口。实现Iterable接口的那些类可以拥有增强的for循环，该循环施加于这些类之上以观察它们所有的项。
二、Iterator接口
实现了Iterable接口的集合必须提供一个称为iterator的方法，该方法返回一个Iterator类型的对象。该Iterator是一个java.util包中定义的接口。
Iterator接口的思路是，通过ierator方法，每个集合均可创建并返回一个实现Iterator接口的对象，并将当前位置的概念在对象内部存储下来。
每次对next的调用都给出集合的（尚未见到的）下一项。因此，第1次调用next给出第1项，第2次调用给出第2项……；hasNext用来判断是否存在下一项；当编译器见到一个正在用于Iterable的对象的增强的for循环的时候，它用对iterator方法的那些调用代替增强的for循环以得到一个Iterator对象，然后调用next和hasNext。
下面给出一段简单的代码：
public class forIterableObject {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<>();
list.add("123");
list.add("456");
print(list);
}
public static <T> void print(Collection<?> collection ){
for (Object o : collection) {
System.out.println(o);
}
}
}相信对Java语言稍有了解的读者都可以理解，这是一段简单的对集合的元素使用增强for遍历并打印的代码。接下来我们来看对应的字节码文件：
public class forIterableObject {
public forIterableObject() {
}
public static void main(String[] var0) {
ArrayList var1 = new ArrayList();
var1.add("123");
var1.add("456");
print(var1);
}
public static <T> void print(Collection<?> var0) {
Iterator var1 = var0.iterator();
while(var1.hasNext()) {
Object var2 = var1.next();
System.out.println(var2);
}
}
}不难看出，在print方法中的增强for通过编译器之后，自动被对应的Iterator对象所代替。可见，Iterable类型上的增强for的底层为迭代器。
Iterator接口中的方法有限，因此很难做遍历之外的操作。
Iterator接口中还有一个名为remove的方法，该方法可以删除由next最新返回的项（直到再次调用next方法之后，不能再调用remove， ）。
虽然Collection接口也包含remove方法，但是Collection的remove方法需要先找出要被删除的项。因此如果知道要删除的项，使用Iterator的remove方法可能开销会更小，如集合中的隔项删除。
直接使用迭代器（非增强for）的基本法则：
如果对正在被迭代的集合进行结构上的改变（增、删等），那么迭代器就不再合法（并且在其后使用该迭代器时会抛出ConcurrentModificationException异常）。为避免迭代器正准备给出的下一项已经被删除或正好有新的一项在此项之前插入，我们只有在需要立即使用一个迭代器的时候，才应该去获取迭代器。
list接口
List接口继承了Collection接口，因此它包含Conllection接口的所有方法，外加其他一些方法。
List接口中的大部分方法的功能都是可通过名称来判断的，这里不再一一解释，详细的使用方法请读者参考JDK API文档
List ADT有两种流行的实现方式，ArrayList和LinkedList.
1）ArrayList类
ArrayList类提供了List ADT的一种可增长数组的实现。ArrayList中有一个容量的概念，它表示基础数组的大小。在需要的时候，ArrayList将自动增加其容量以保证至少具有表的大小。
优点：使用get和set的调用，花费常数时间，时间复杂度为O(1) 。
缺点：新项的插入和删除代价昂贵，除非是在ArrayList的末端。
2）LinkedList类
LinkedList类提供了List ADT 的双链表实现。
优点：（假设变动项位置已知）新项的插入和删除开销很小。这意味着，表的前端进行添加和删除都是常数时间的操作，时间复杂度为O(1)，由此LinkedList提供了addFirst、removeFirst等操作。
缺点：不容易索引，因此对get方法的调用是昂贵的，除非调用非常接近表的端点。
3）时间复杂度分析
a）表尾插入
//表尾插入比较
public static void makeList1(List<Integer> lst, int n){
lst.clear();
for (int i = 0; i < n; i++) {
lst.add(i);
}
}这里，不管ArrayList还是LinkedList作为参数被传递，makeList1的运行时间都是O(N)，因为对add的每次调用都是在表的末端，花费常数时间。
b）表头插入
//表头插入比较
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²)，因为在ArrayList中，在前端添加是一个O(N)操作。
c）遍历求和
//求和运算比较
public static int makeListSum(List<Integer> lst, int n){
int total = 0;
for (int i = 0; i < n; i++) {
total += lst.get(i);
}
return total;
}这里ArrayList的运行时间是O(N)，但对于LinkedList来说，其运行时间则是O(N²)，因为在LinkedList中，对get的调用是O(N)操作。
但是，如果这里使用增强for，那么它对任何List的运行时间都是O(N)，因为迭代器将有效的从一项到下一项推进。
d）搜索
对搜索而言，ArrayList和LinkedList都是低效的，对Colletion的contains和remove方法的调用均花费线性时间，时间复杂度为O(N)。