本节我们将做以下测试：删除一个表中的所有偶数元素，并寻求最忧解
一、方法选择
方法1：
构建一个包含原表所有奇数的新表，然后清除原表并将新表拷贝回原表。
当然，这种做法显然比较糟糕，不但要求我们事先知道原表的所有奇数，还有创建新的对象。
方法2：
在原表中进行遍历，遇到偶数元素，将其删除。
这种做法是十分常见的解决方案，但是，这对于ArrayList来说几乎是一个失败的策略。因为从一个ArrayList执行删除操作开销很大。不过，对于LinkedList，这种做法却存在希望，因为从已知的位置上删除的操作可以通过重新安排某些链而被有效的完成。
二、代码优化
通过上面的分析，我们显然选择第二种方案。
代码1：
public static void removeElement1(List<Integer> list){
int i = 0;
while (i < list.size()){
if (list.get(i) % 2 == 0){
list.remove(i);
}else {
i++;
}
}
}对于初学者，这是一段相当常见的遍历删除的代码。虽然逻辑上没有任何问题，但是效率却十分低下。
在一个ArrayList上，remove的效率不是很高（需要移动后方的所有元素），因此程序的时间复杂度是平方级的。
而对于LinkedList，首先get的调用效率就十分低下，其次remove的调用效率也不高，因为到底打i的代价是昂贵的（通过外层循环），因此时间复杂度也是平方级的。
代码2：
public static void removeElement2(List<Integer> list){
for (Integer x : list) {
if (x % 2 == 0){
list.remove(x);
}
}
}经过改造之后，我们的代码看上去就简洁了许多。
这样的写法是使用一个迭代器一步步遍历该表，这是高效率的。
但是，问题并没有被完全解决，因为我们所使用的是Conllection的remove方法，这个方法必须再次搜索该项（线性时间 O(N)）。但这并不是最可怕的，当我们运行程序的时候会发现，竟然抛出了异常。
导致这种结果的原因是我们不能期待增强for知晓下一项是否会被删除，具体的使用法则，请参考Collection API。
代码3：
public static void removeElement3(List<Integer> list){
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
if (iterator.next() % 2 == 0){
iterator.remove();
}
}
}再次改造代码之后，我们的出了一种成功的方案：在迭代器找到一个偶数项时，使用迭代器来将其删除。
对于一个LinkedList，对该迭代器的remove方法的调用只花费常数时间（时间复杂度，O(1)），因为调用时，迭代器正好位于当前项（要被删除的节点）或在其附近。因此，对于LinkedList，整个程序花费线性时间，时间复杂度O(N)。
对于一个ArrayList，其remove方法的开销仍然很大，因为要移动数组元素。因此，对ArrayList整个程序仍花费二次时间，时间复杂度O(N²)。
三、测试数据
因为此处的测试将花费大量的时间，所以笔者直接借用 Mark Allen Weiss 的测试结果，有时间的读者可以自行测试。
根据《数据结构与算法分析（Java语言描述）》的作者Mark Allen Weiss的测试，得出如下结果：
对于最终的程序：
- LinkedList，400000项的花费时间是0.031秒，800000项的花费时间是0.062秒
- ArrayLiset，400000项的花费时间约为2.5分钟，800000项的花费时间约为10分钟
由此可见，我们的上述时间复杂度分析结果正确。