数据结构与算法（Java）-007-JAVA COLLECTIONS API中的表

• 在类库中，java包含了一些基本数据结构的实现，表ADT是在Collections API中实现的数据结构之一。

COLLECTION接口

• Collections API位于java.util包中，集合（collection）的概念在Collection接口中得到抽象，它存储一组类型相同的对象。下面包含了该接口的方法。
  

在Collection接口中的许多方法所做的工作由它们的英文名称可以看出：

• size返回集合中的项数；
• isEmpty返回true当且仅当集合的大小为0。
• 如果x在集合中，则contain返回 true。注意，这个接口并不规定集合如何决定x是否属于该集合，这要由实现该Collection 接口的具体的类来确定。
• add和remove从集合中添加和删除X，如果操作成功则返回true。如果因某个看似有理(非异常)的原因失败则返回false。例如，如果要删除的项不在集合中，则remove可能失败，而如果特定的集合不允许重复，那么当企图插人一项重复项时，add操作就可能失败。
• Collection接口扩展了 Iterable接口。实现Iterable接口的那些类可以拥有增强的for循环，该循环施于这些类之上以观察它们所有的项。

ITERATOR接口

• 实现Iterator接口的类必须要实现其中Iterator方法，该方法返回一个Iterator类型的对象。Iterator是一个在java.util包中定义的接口。

• Iterator接口的思路是，通过iterator方法，每个集合都可以创建并返回给用户一个实现了Iterator接口的对象，并将当前位置的概念在对象内部存储下来。
• 每次对next方法的调用都给出集合的下一项（尚未见到的），所以，第n次调用next方法给出第n项。
• hashNext方法来检测下一项是否存在。
• 当编译器看到一个正在用于Iterator的对象的增强循环时，它会用Iterator去替代增强for循环以得到一个Iterator对象，然后调用next方法和hasNext方法。所以集合的增强for循环会被编译器重写成Iterator形式，如：

public static <T> void print(Collection<T> coll) {
    for(T item : coll) {
        System.out.println(item);
    }
}

会被编译器重写成：

public static <T> void print(Collection<T> coll) {
    Iterator<T> iterator = coll.iterator();
    while (iterator.hasNext()) {
        T item = iterator.next();
        System.out.println(item);
    }
}

• 由于Iterator接口中的现有方法有限，因此，很难使用Iterator做简单遍历Collection以外的任何工作。

• Iterator接口还包含一个方法，叫做remove。该方法可以删除由next最新返回的项(此后，我们不能再调用remove，直到对next再一次调用以后）。

• 虽然Collection接口也包含一个remove方法，但是，使用Iterator的remove方法可能有更多的优点。Iterator的remove方法的主要优点在于，Collection的remove方法必须首先找出要被删除 的项。如果知道所要删除的项的准确位置，那么删除它的开销很可能要小得多。在集合中每隔一项删除一项。这个程序用迭代器(iterator)很容易编写，而且 比用Collection的remove方法潜藏着更髙的效率。
• 当直接使用Iterator(而不是通过一个增强的for循环间接使用)时，重要的是要记住一个基 本法则：如果对正在被迭代的集合进行结构上的改变（即对该集合使用add、remove或clear方法)，那么迭代器就不再合法（并且在其后使用该迭代器时将会有ConcurrentModi-ficationException异常被抛出）。为避免迭代器准备给出某一项作为下一项(next item)，而该项此后或者被删除，或者也许一个新的项正好插人该项的前面这样一些讨厌的情形，有必要记住上述法则。这意味着，只有在需要立即使用一个迭代器的时候，我们才应该获取迭代器。然而，如果迭代器调用了它自己的remove方法，那么这个迭代器就仍然是合法的。这是有时候我们更愿意使用迭代器的remove方法的第二个原因。

LIST接口、ARRAYLIST接口、LINKEDLIST类

• List接口继承了Collection接口，所以它含有Collection接口中的所有方法，另外再新增了一些别的方法。下面包含了一些重要的方法：

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

    ListIterator<AnyType> listIterator(int pos);
}

• get和set使得用户可以访问或改变通过由位置索引index给定的表中指定位置上的项。索引0位于表的前端，索引size()-1代表表中的最后一项，而索引size()则表示新添加的项可以被放置的位置。add使得在位置index处置入一个新的项（并把其后的项向后推移一个位置）。于是,在位置0处add是在表的前端进行的添加，而在位置size()处的add是把被添加项作为新的最后项添人表中。除以AnyType作为参数的标准的remove外，remove还被重载以删除指定位置上的项。最后，List接口指定listIterator方法，它将产生比通常认为的还要复杂的迭代器。
• List ADT有两种流行的实现方式。ArrayList类提供了List ADT的一种可增长数组的实现。使用ArrayList的优点在于，对get和set的调用花费常数时间。其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在ArrayList的末端进行。LinkedList类则提供了List ADT的双链表实现。使用LinkedList的优点在于，新项的插入和现有项的删除均开销很小，这里假设变动项的位置是已知的。这意味着，在表的前端进行添加和删除都是常数时间的操作，由此LinkedList更提供了方法addFirst和removeFirst、addLast和removeLast、以及getFirst和getLast等以有效地添加、删除和访问表两端的项。使用LinkedList的缺点是它不容易作索引，因此对get的调用是昂贵的，除非调用非常接近表的端点（如果对get的调用是对接近表后部的项进行，那么搜索的进行可以从表的后部开始)。为了看出差别，我们考察对一个List进行操作的某些方法。首先，设我们通过在末端添加一些项来构造一个List。

REMOVE方法对LINKEDLIST的应用

• 作为一个例子，提供一个例程，将一个表中所有具有偶数值的项删除。于是，如果表包含6,5,1,4,2,则在该方法调用之后，表中仅有元素5,1。
• 当遇到表中的项时将其从表中删除的算法有几种可能的想法：当然，一种想法是构造一个包含所有的奇数的新表，然后清除原表，并将这些奇数拷贝回原表。不过，我们更有兴趣的是写一个干净的避免拷贝的表，并在遇到那些偶数值的项时将它们从表中删除。
• 对于ArrayList这几乎就是一个失败策略。因为从一个ArrayList的几乎是任意的地方进行删除都是昂贵的操作。不过，在LinkedList中却存在某种希望，因为我们知道，从已知位置的删除操作都可以通过重新安排某些链而被有效地完成。
• 第一种想法。在一个ArrayList上，我们知道，remove的效率不是很高的，因此该程序花费的是二次时间。LinkedList暴露两个问题。首先，对get调用的效率不高，因此例程花费二次时间。而且，对remove的调用同样地低效，因为达到位置i的代价是昂贵的。

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

• 另一种想法。我们不是用get,而是使用一个迭代器一步步遍历该表。这是高效率的。但是我们使用Collection的remove方法来删除一个偶数值的项。这不是高效的操作，因为remove方法必须再次搜索该项，它花费线性时间。但是我们运行这个程序会发现情况更糟：该程序产生一个异常，因为当一项被删除时，由增强的for循环所使用的基础迭代器是非法的（异常：java.util.ConcurrentModificationException）。

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

• 成功的想法：在迭代器找到一个偶数值项之后，我们可以使用该迭代器来删除这个它刚看到的值。对于一个LinkedList,对该迭代器的remove方法的调用只花费常数时间，因为该迭代器位于需要被删除的节点(或在其附近)。因此，对于LinkedList，整个程序花费线性时间，而不是二次时间。对于一个ArrayList，即使迭代器位于需要被删除的节点上，其remove方法仍然是昂贵的，因为数组的项必须要移动，正如所料，对于ArrayList,整个程序仍然花费二次时间。

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

• 如果我们传递一个LinkedList运行上面的程序，对于一个400000项的lst,花费的时间是0.031秒，而对于一个800000项的LinkedList则花费0.062秒，显然这是线性时间例程，因为运行时间与输人大小增加相同的倍数。当我们传递一个ArrayList时，对于一个400000项的ArrayList程序几乎花费2.5分钟，而对于800000项的ArrayUst程序花费大约10分钟；当输人增加到2倍时运行时间增加到4倍，这与二次的特征是一致的。

LISTITERATOR接口

• Listlterator扩展了List的Iterator的功能。方法previous和hasPrevious使得对表从后向前的遍历得以完成。
• add方法将一个新的项以当前位置放人表中（next项之前）。当前项的概念通过把迭代器看做是在对next的调用所给出的项和对previous的调用所给出的项之间而抽象出来的。下图解释了这种抽象。对于LinkedList来说，add是一种常数时间的操作，但对于ArrayList则代价昂贵。
• set改变被迭代器看到的最后一个值，对LinkedList很方便。这对于LinkedList来说，不使用Listlterator的set方法是很难做到的。

public interface ListIterator<AnyType> extends Iterator<AnyType> {
    public boolean hasPrevious();
    public AnyType previous();

    public void add(AnyType x);
    public void set(AnyType newVal);
}

---

其它

源码下载：

关注下方微信公众号，
回复：
DS-AA-Java.code

• 欢迎加入交流群：451826376

• 更多信息：www.itcourse.top