Java核心技术 卷1 基础知识—集合

《第九章 集合》 一.Java集合框架 1.将集合的接口和实现分离

与现代的数据结构类库的常见情况一样，Java的集合类库将接口(interface)与实现(implement)分离
那么什么是接口与实现分离呢？
Java类库中关于Queue接口的定义如下：

public interface Queue<E> extends Collection<E> { boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); }

可以看到Queue接口并没有说明队列是如何实现的，这其实就实现了接口与实现的分离
因为接口本身就没有涉及到具体的实现，具体实现由接口的实现类来实现
队列通常有两种实现方式：一种是使用循环数组；另一种是使用链表
在Java类库中，如果需要一个循环数组队列，可以使用ArrayDeque类
ArrayDeque类的定义如下：

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable { //Deque接口extends Queue接口 ... }

如果需要一个链表队列，可以使用LinkedLList类
LinkedList类的定义如下：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { //Deque接口extends Queue接口 ... }

因为，接口与实现的分离，所以可以使用接口类型存放集合的引用

//链表实现的队列 Queue<Integer> queue = new LinkedList<>(); queue.add(100); //数组实现的队列 Queue<Integer> queue = new ArrayDeque<>(); queue.add(100);

在Java类库中，还存在另外一组以Abstract开头的类
例如上面代码中的AbstractCollection，AbstractSequentialList
这些类是为类库实现者而设计的，例如想要实现自己的Collection类
会发现扩展AbstractCollection类要比实现Collection接口中的所有方法轻松得多

2.Collection接口

在Java类库中，集合类的基本接口之一就是Collection接口
Collection接口有两个基本方法

public interface Collection<E> extends Iterable<E> { boolean add(Element); Iterator<E> iterator(); ... }

add添加元素，如果添加后改变了集合就返回true；
iterator方法用于依次访问集合中的元素
而且Collection接口还扩展了Iterable接口
所以对于所有的Collection接口的实现类都可以使用"for each"循环

3.迭代器

迭代器Iterator接口包含4个方法

public interface Iterator<E> { boolean hasNext(); E next(); default void remove() { throw new UnsupportedOperationException("remove");} default void forEachRemaining(Consumer<? super E> action) { Object.requireNonNull(action); while (hasNext()) action.accept(next()); }

反复调用next方法，可以逐个访问集合中的每个元素
但是到了集合的末尾，next方法会抛出一个NoSuchElementException
因此需要在调用next之前先调用hasNext方法

Iterator接口的remove方法将会删除上次调用next方法返回的元素
如果调用remove之前没有调用next将是不合法的

forEachRemaining方法的参数可以是一个lambda表达式
执行该方法时将对迭代器的每一个元素调用lambda表达式
iterator.forEachRemaining(elememnt->do something with element)

4.集合框架中的接口：

Java集合框架为不同类型的集合定义了大量接口

可以看到，集合中有两个基本接口：Collection和Map
Map接口插入元素时使用put方法，从键值对中读取值就需要get方法
SortedSet和SortedMap接口会提供用于排序的比较器对象

二.具体的集合

下图主要展示了Java类库中的集合，并简要介绍了每个集合类的用途（不包括线程安全集合）
除了以Map结尾的类之外，其他类都实现了Collection接口
而以Map结尾的类实现了Map接口

集合框架中的类

1.链表

众所周知，数组擅长随机访问，但不擅长删除或者插入元素
而链表则是擅长移动或者插入元素，但访问数据是只能按顺序访问，效率比较慢

在Java中，所有链表实际上都是双向链表——即每个结点还存放着指向前驱节点的引用
在数据结构这门课中，我们知道要想在链表中插入或者删除元素，就需要将节点的指针“绕来绕去”
但在Java中美则不同，其对链表LinkedList的插入或者删除非常简单，举例如下：
先添加3个元素，再将第二个元素删除

List\<String\> staff = new LinkedList<>(); /*构造链表*/ staff.add("Amy");//在链表的末尾添加元素 staff.add("Bob"); staff.add("Carl"); /*删除元素*/ Iterator iter = staff.iterator(); String first = (String)iter.next(); String second = (String)iter.next(); iter.remove();//remove方法将会删除上次调用next方法返回的元素 /*插入元素*/ ListIterator<String> listIterator = staff.listIterator(); listIterator.next(); listIterator.add("Juliet");//在Bob之前插入Juliet

可以看出上面的代码并没有让指针“绕来绕去”
它利用了Iterator接口的remove方法来实现链表的删除
利用ListIterator接口的add来实现列表的插入

另外，ListIterator接口有两个方法，可以用来反向遍历链表

E previous() boolean hasPrevious() 2.数组列表