18.2.2　List链表接口和Set接口

List接口和Set接口是两个非常有用的集合接口，日常开发中用到的数组和列表等，基本上都从这两个接口实现而来。本节通过对它们的比较，详细了解这两种集合接口。

1.List接口

List接口是有序的Collection，使用此接口能够精确地控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

与下面所提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator（）方法外，List还提供listIterator（）方法，其返回ListIterator接口。与标准的Iterator接口相比，ListIterator多了一些add（）之类的方法，允许添加、删除、设定元素，还能向前或向后遍历。

实现List接口的常用类有LinkedList、ArrayList、Vector和Stack。

（1）LinkedList链表类。LinkedList实现了List接口，允许null元素。此外，LinkedList在首部或尾部提供额外的get（）、remove（）、insert（）方法，这些操作使LinkedList可被用作堆栈（stack）、队列（queue）或双向队列。

LinkedList没有同步方法，如果多个线程同时访问一个List，则必须自己实现访问同步，一种解决方法是在创建List时构造一个同步的List。

List list=Collections.synchronizedList（new LinkedList（……））；

（2）ArrayList数组列表类。ArrayList实现了可变大小的数组，它允许所有元素，包括null。ArrayList没有同步。

每个ArrayList实例都有一个容量（Capacity），即存储元素的数组的大小，这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可调用ensureCapacity（）方法来增加ArrayList的容量，以提高插入效率。与LinkedList一样，ArrayList也是非同步的（unsynchronized）。

（3）Vector存储类。Vector非常类似ArrayList，但Vector是同步的。由Vector创建的Iterator和ArrayList创建的Iterator是同一接口。当Iterator被创建而且正在被使用时，另一个线程改变了Vector的状态（例如添加或删除了一些元素），因Ve c t o r是同步的，这时调用I t e r a t o r的方法将抛出ConcurrentModificationException，因此必须捕获该异常。

（4）Stack栈类。Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法，使得Vector被当作堆栈使用。Stack有基本的push（）、pop（）方法，还有peek（）方法，用来得到栈顶的元素。empty（）方法测试堆栈是否为空。search（）方法检测一个元素在堆栈中的位置。新创建的Stack是空栈。

2.Set接口

Set是一种不包含重复元素的Collection，即任意的两个元素e1和e2比较，结果都不相等，如e1.equals（e2）=false。Set最多有一个null元素。

注意

Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态，Object.equals（Object）=true会发生一些问题。