JAVA中的Collection接口和其主要实现的类

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set,详细信息可见官方文档http://tool.oschina.net/uploads/apidocs/jdk-zh/java/util/Collection.html,下面我们来讨论继承它的接口list,Set，这两个接口实现了主要的方法，但是还是有一些拓展的，不如list中的迭代就和collection中的有些不同，下面会详细介绍，这里我们用一个例子体会一下这里的接口的实现：

 Collection<Integer> list=new LinkedList<>();  

list

• list是有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
• list与Set不同，list允许重复的元素插入
• list接口提供了两种在列表的任意位置高效插入和移除多个元素的方法。
• 下面我们来具体介绍一下它的实现的类

LinkedList

从文档中可以看到这个listedList实现的不只是list接口，比如还是实现了Deque接口，这个为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。这里的LinkedList都是用双向链表实现的，这个类不是同步的，因此在多个线程中有修改其中的元素操作时必须实现外部的线程同步

构造方法

• LinkedList() 创建一个空的链表
• LinkedList(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列,构造如下：

        ArrayList<Integer> arrayList=new ArrayList<>();  //这里新建一个线性列表
        LinkedList<Integer> linkedList=new LinkedList<Integer>(arrayList);  //用线性列表新建一个链表
        System.out.println(linkedList.getFirst());      

方法摘要

• boolean add(E e) 将指定元素添加到此列表的结尾。成功插入返回True
• void add(int index, E element) 在此列表中指定的位置插入指定的元素。
• boolean addAll(Collection<? extends E> c) 添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。例子如下：

 ArrayList arrayList=new ArrayList();//新建一个线性表
        arrayList.add(10);
        arrayList.add(100);
        arrayList.add(2);
        LinkedList linkedList=new LinkedList();
        linkedList.add(100);
        linkedList.add("chenjiabing");

        linkedList.addAll(arrayList);  //将线性表中所有的元素添加到链表中
        for(Object i:linkedList)
        {
            System.out.println(i);
        }

• boolean addAll(int index, Collection<? extends E> c) 将指定 collection 中的所有元素从指定位置开始插入此列表。
• addFirst 将指定的元素添加到开头
• addLast 将指定的元素添加到末尾
• clear() 从列表中移除全部的元素
• clone() 得到一个链表的副本，由于其返回的类型是Object，因此需要进行强制转换成LinkedList类型

 LinkedList list=(LinkedList)linkedList.clone();

• contains(Object o) 如果此列表中包含元素o返回True
• element() 获取但不移除此列表的头（第一个元素）。
• iterator() 返回列表中的元素的迭代器

Iterator iter=list.iterator();      //返回一个迭代器类型
while(iter.hasNext())     //判断迭代器中是否存在元素
{
    Object o=iter.next();    
    if(o.equals(1))
    {
    System.out.println(o);   //输出迭代器中的元素
    iter.remove();   //移除这个元素，这个是从列表中直接移除的
}
    
}

• listIterator() 返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始

ListIterator iterator = list.listIterator();
        while (iterator.hasNext())     //首先将迭代器一直运行到末尾
        {
            Object o = iterator.next();
            if (o.equals(1)) {
                iterator.add(100);   //将元素插入到当前元素的前面，这个在Iterator是不存在的方法
            }

        }

        while (iterator.hasPrevious())   //这时的迭代器是从末尾开始的，因此这里相当与逆序输出
        {
            System.out.println(iterator.previous());
        }

• get(int index) 返回此列表中指定位置处的元素。这里要注意的是虽然这种方式能够得到指定索引的值，但是这里对于链表中的操作开销是非常大的，因此这个方法不主张使用，如果需要遍历列表可以使用迭代器和for-each语句

LinkedList list=new LinkedList();
for(int i=0;i<10;i++)
{
    list.add(i);
}
for(Object o:list){     //使用for-each遍历列表
System.out.println(o); 
}

Iterator iter=list.iterator();      //返回一个迭代器类型

while(iter.hasNext())     //判断迭代器中是否存在元素
{
    System.out.println(iter.next());   //输出迭代器中的元素
}

• getFirst() 返回此列表的第一个元素。
• getLast() 返回此列表的最后一个元素
• indexOf(Object o) 返回元素第一次出现的索引
• lastIndexOf(Object o) 返回元素最后一次出现的索引
• toArray() 返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组
• set(index,element) 将指定索引的元素替换成element
• size() 返回元素的个数
• remove() 移除表头的元素
• remove(index) 移除此列表中指定位置处的元素。

ArrayList

• List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）
• 每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。
• 注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来

构造函数

• ArrayList() 构造一个初始容量为 10 的空列表。
• ArrayList(Collection<? extends E> c) 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
• 构造一个具有指定初始容量的空列表。

方法摘要

由于和LinkedList继承了同一个接口，因此大部分的函数都是相同的，只是在拓展了一些特有的方法，共有的方法有：add,addAll,get,clone,clear,contains,indexOf,remove,set,size,toArray,lastIndexOf,iterator,listIterator。特有的方法如下：

• isEmpty() 如果此列表中没有元素，则返回 true
• void trimToSize() 将此 ArrayList 实例的容量调整为列表的当前大小。因为这里的线性列表的容量会随着加入的元素而增加，因此这个函数的作用就是将线性列表的的容量变成当成元素的大小

Vector

• Vector类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作
• 每个向量会试图通过维护 capacity 和 capacityIncrement 来优化存储管理。capacity 始终至少应与向量的大小相等；这个值通常比后者大些，因为随着将组件添加到向量中，其存储将按 capacityIncrement 的大小增加存储块。应用程序可以在插入大量组件前增加向量的容量；这样就减少了增加的重分配的量。
• 从源码中可以看出Vector是线程安全的，源码中的插入和删除操作都实现了进程的同步语句块，因此Vector的插入和删除是比较低效的

构造函数

• Vector() 构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零。
• Vector(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的向量，这些元素按其 collection 的迭代器返回元素的顺序排列。
• Vector(int initialCapacity) 使用指定的初始容量和等于零的容量增量构造一个空向量。
• Vector(int initialCapacity, int capacityIncrement) 使用指定的初始容量和容量增量构造一个空的向量。

注意:使用第一种方法系统会自动对向量进行管理，若使用后两种方法。则系统将根据参数，initialcapacity设定向量对象的容量（即向量对象可存储数据的大小），当真正存放的数据个数超过容量时。系统会扩充向量对象存储容量.

方法摘要

同样是继承了List接口，因此大部分的方法都是一样的，比如add,addAll,clear,clone,contains,remove,removeall

stack

Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。
注意：这里的stack虽然继承了了Iterator接口但是如果使用了迭代的话它输出的还是原来你输入的顺序，这里就违背了栈的原理后进先出

构造方法

• Stack() 创建一个空堆栈。

方法摘要

• isEmpty() 测试堆栈是否为空。
• peek() 查看堆栈顶部的对象，但不从堆栈中移除它。
• pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象。
• push(E element) 把项压入堆栈顶部。
• search(Object o) 返回对象在堆栈中的位置，以 1 为基数。