Java数组和集合

一、集合的概念
        集合是源于数学中的术语，集合的一些原理和算法来自于数学中的理论。在java中，集合类是用来存放对象的。对于集合的使用是通过实例化集合类得到集合对象。而集合对象则代表以某种方式组合到一起的一组对象，对于这组对象的使用是通过引用集合对象来进行的。
通过班级的例子来给集合举例：（示意代码如下）
        班级集合 班级A = new 班级集合（）// 班级A代表班级对象引用
        // 在班级里添加学生
        班级A.加入学生方法（学生对象A) ;
        班级A.加入学生方法（学生对象B) ;
       // 使用集合内对象
        学生 学生对象1 = （学生）班级A.取得一个对象（）；
        学生对象1 . 学生对象自己的方法（）；
        。。。。。
        。。and so on。。。
     通过例子，我们看看是否有共性的部分可以提取出来呢？经分析，我们发现：
（1）、集合的操作都是相似的，向集合内添加元素（存储），从集合中取得元素（检索），从集合中删除元素，修改集合的某个元素（注意，不是修改元素本身属性），还有其他操作（元素排序等）
（2）、集合都是用来存储对象的（集合内存储的每个对象我们称为元素或者元素对象）
（3）、集合要有一定的容量，能过存放多个元素。

数组就可以实现上面的需求，但java里面还有一些重要的API来实现集合类也能实现，这时候，你就会问了，既然数组能实现容纳对象的容器功能，为什么还要设计这些集合类呢？
下面就看看集合和数组的区别：（写一个程序例子）
import java.util.ArrayList;

public class StudentDemo {
        //学生类
        private String name;
        private int age;
        public StudentDemo(String name, int age){
                this.name = name;
                this.age = age;
        }
  
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //先写一个数组的例子
                StudentDemo[] sArray = new StudentDemo[3];
                sArray[0]=new StudentDemo("jack",20);
                sArray[1]=new StudentDemo("marry",18);
                sArray[2]=new StudentDemo("terry",22);
                StudentDemo stu1 = sArray[0];
                System.out.println("this is array="+stu1.name+"   this age="+stu1.age);
                //在写一个集合的例子
                ArrayList coll = new ArrayList();
                coll.add(new StudentDemo("marryone",18));
                coll.add(new StudentDemo("jackone",22));
                coll.add(new StudentDemo("terryone",23));
                StudentDemo stu2 = (StudentDemo)coll.get(0);
                System.out.println("this is coll= "+stu2.name+"    this is age"+stu2.age);
        }

}
从例子中来比较一下数组和集合的区别:
(1).数组的长度是固定的，在定义数组的时候，就要确定数组长度大小。而集合类在定义的时候不需要确认集合所能容纳对象的数量，也就是说集合的大小是动态调整的。在实际应用中我们不能确认的需要存放元素数量的时候，采用集合是比较好的。容量可变是集合相对于数组的最大区别之一。
   （2）数组既可以容纳基本数据类型，也可以容纳对象。而集合只能容纳对象，不容纳基本数据类型。另外，需要强调一点的是，无论是数组还是容器，当其容纳对象的时候，存放的都是对象的引用。而数组在容纳基本数据类型的时候，持有的则是数值。
（3） 如果想在集合中容纳基本数据类型，该怎么做呢？
        当我们把一个对象放到集合中，该对象好像“失去”了它的型别特征，以后在使用的时候，除非使用者知道存入对象的类型，否则无法正确使用该对象。所以要像上面的例子一样，要进行一次强制类型的转化
StudentDemo stu2 = (StudentDemo)coll.get(0);将其转化为原来存储时的对象。

二，在谈谈数组
        在数组的处理上，除了数组本身提供的特性外，java还实现了一个工具类Arrays，提供了部分公用的static方法增强数组的处理功能。
        介绍下Arrays工具类的公用方法
        fill()    -------     将某个数值填入到数组内
        sort()  -------    对数组内的元素进行排序
        binarySearch() ------  在已排序的数组中查找
        asList() ------   把数组转换为List
等等还有一些其他的方法，这里就先介绍下sort()和binarySearch()的用法吧，一样也是要用例子来说明的：
        1，先说说sort()吧，排序需要对数组内元素进行比较，基本数据类型（比如数字、字符串）等是比较简单的。
但是，对于对象的比较，还是需要进行一些额外的处理的。比如，对于一份学生的考试成绩单来说，成绩单包含的信息如学生的学号，姓名，成绩等。我们要排序的时候，就要确定要按照成绩单的那个属性进行排序的。

        对于对象的比较，有两种方法来实现。
第一种方法：欲比较的类实现Comparable接口，该类就具有了比较的能力。而实现该类接口的时候，只有一个方法compareTo() 需要实现，该方法接受另外一个对象作为比较参数，两个对象相等时返回0，该对象小于参数对象的时候，就返回正值，大于返回负值。类实现Comparable接口后，可以调用Arrays.sort()方法对数组内的类对象进行排序。
如：
        import java.util.Arrays;
   import java.util.Collections;
   public class TestResult implements Comparable {

        int point;
        int no;
        String name;
       
        public TestResult(int point,int no,String name){
                this.point = point;
                this.no = no;
                this.name = name;
        }
       
       
        public int compareTo(Object o) {
               
                int point_cp = ((TestResult)o).point;
                return (point < point_cp ? -1:(point == point_cp ? 0:1));
        }
       
        public static void main(String[] args) {
                TestResult[] tra = { new TestResult(90,2,"ahang"),new                        TestResult(80,3,"wang"),new TestResult(100,1,"zhao")};
                Arrays.sort(tra);
                /*使用Arrays.sort()默认的排序是升序的，那我们想要降序排列的话就使用下面的一句话就可以了*/
                //Arrays.sort(tra,Collections.reverseOrder());
                for(int i = 0, trsleng = tra.length; i<trsleng;i++){
                        System.out.println(tra[i].name + ","+tra[i].point);
                       
                }
        }
}

执行结果如下：
wang,80
ahang,90
zhao,100

第二种方法：如果我们拿到一个类，但是这个类没有实现Comparable接口，或者我们不想使用该类默认实现的Comparable接口的比较方法，我们想采用自己的思路来排序。变通的做法就是新创建一个比较算法类，该类实现的是Comparator接口（不是Comparable接口了），实现的时候，比较方法参数的2个对象。该比较类不是具体的比较参与对象，知识算法提供者（comparator），在需要使用排序的时候，该算法作为参数传递给排序方法。（红色字部分说的不是很简单命了，其实我理解就是，自己写了一个排序的方法，然后把要排序的对象做为参数传递进去，排序后在有该方法返回一个排序完的结果）
例子如下：

import java.util.Arrays;
import java.util.Comparator;

/**
* 功能：由自己创建一个类并实现Comparator接口，来完成数组对对象的排序
* 作者：jackrui
* 时间：2009.3.27
*/
class ComResult implements Comparator{

        public int compare(Object o1, Object o2) {
                int no1 = ((TestResultComparator)o1).no;
                int no2 = ((TestResultComparator)o2).no;
               
                return (no1<no2?-1:(no1 == no2 ?0:1));
        }
       
}

public class TestResultComparator implements Comparable{
       
        int point;
        int no;
        String name;
       
        public TestResultComparator(int point,int no,String name){
                this.point = point;
                this.no = no;
                this.name = name;
        }
       
        public int compareTo(Object o) {
                int point_cp = ((TestResultComparator)o).point;
                return (point<point_cp ?-1:(point == point_cp?0:1));
        }
       
        public static void main(String[] args) {
                TestResultComparator[] ra = {
                                                new TestResultComparator(90,1,"marry"),
                                                new TestResultComparator(100,2,"jackRui"),
                                                new TestResultComparator(80,3,"Andy"),       
                };
                        //为了比较出区别，所以这里把2个实现比较的方法接口都实现了，如果用到下面这个 就可以不用实现Comparable接口
                        Arrays.sort(ra, new ComResult());
                        //下面的的注释就是要实现Comparable接口才能实现比较
           //Arrays.sort(ra);
                        for(int i = 0,raLength = ra.length; i < raLength;i++){
                                System.out.println(ra[i].name+ ","+ra[i].no);
                        }
        }
}

     2、在数组中进行查找

如何查找元素，我们在数据结构中已经学到了很多的算法，当很多算法强调的重要的一点是：数据要先排序，后查找。排序后的数组可以使用一些快速的查询算法，效率会更高。
Arrays.binarySearch() 就是这这种策略的一个实现，在数据结构和算法中，该方法称为2分法。
现在改造一下上面的例子，变成如下的代码
import java.util.Arrays;
import java.util.Comparator;

/**
* 功能：由自己创建一个类并实现Comparator接口，来完成数组对对象的排序
* 作者：jackrui
* 时间：2009.3.27
*/
class ComResult implements Comparator{

        public int compare(Object o1, Object o2) {
                int no1 = ((TestResultComparator)o1).no;
                int no2 = ((TestResultComparator)o2).no;
               
                return (no1<no2?-1:(no1 == no2 ?0:1));
        }
       
}

public class TestResultComparator{
       
        int point;
        int no;
        String name;
       
        public TestResultComparator(int point,int no,String name){
                this.point = point;
                this.no = no;
                this.name = name;
        }

        public static void main(String[] args) {
               
                ComResult cm =  new ComResult();
                TestResultComparator marry =
                                new TestResultComparator(90,3,"marry");
                TestResultComparator jackRui =
                                new TestResultComparator(100,2,"jackRui");
                TestResultComparator Andy =
                                new TestResultComparator(80,1,"Andy");
                TestResultComparator billy =
                                new TestResultComparator(60,4,"billy");
               
                TestResultComparator[] ra = {marry,jackRui,Andy};
               
               
                        Arrays.sort(ra,cm);
                        //Arrays.sort(ra);
                        //排序后进行查找
/*此处排序后的查找要注意的是，当使用第一种写法的时候，即实现comparable来进行排序的时候，下面的Arrays.binarySearch(ra, jackRui,cm)可以不用写cm，如果要是采用第2种写法的时候，一定要写这个，不然的话，会报出错的信息*/
                        int index1 = Arrays.binarySearch(ra, jackRui,cm);
                        int index2 = Arrays.binarySearch(ra, marry,cm);
                        int index3 = Arrays.binarySearch(ra, Andy,cm);
                        int index4 = Arrays.binarySearch(ra, billy,cm);
                       
                        for(int i = 0,raLength = ra.length; i < raLength;i++){
                                System.out.println(ra[i].name+ ","+ra[i].no);
                        }
                        System.out.println();
                        System.out.println();
                        System.out.println(index1);
                        System.out.println(index2);
                        System.out.println(index3);
                        System.out.println(index4);
                                               
        }  
}
  执行结果如下：
Andy,1
jackRui,2
marry,3


1
2
0
-4

解析：输出的结果大于等于0 表示查找到该元素，并且返回元素在数组中的索引值。
            输出的结果小于0，则表示没有找到该元素，负值的大小表示如果该元素要插入到数组中的索引号。
            需要注意的是：如果排序采用的是第2种方法，也就是单独写排序算法的类提供comparator，则在查找的时候，也要采用该comparator。就像我写的这个例子一样。


                             java2 集合框架层次结构

1.1 java2集合
         java2 的集合框架除了提供可变容量的“容器”特性外，还丰富了一些其他数据结构的实现，比如链表（linked-list），队列（queue）

        java2集合主要包含2大类：
                       A、 collection：collection内包含着一组单独的元素，而根据元素存放规则又分为

                                        （1）、List：以线性方式存储，元素存储有特定顺序，元素可以重复。
                                        （2）、Set：集合内元素不可以重复，Set内元素是无序的。
                       B、Map：一群以Key/value（键/值对）构成的成对对象集合，集合内的每个元素都包含2个对象--也就是成对对象。这种存储模式类似于数据库中一条记录的存储，该记录包含主键（key字段）和其他字段（组成value值），当我们想查一条记录的时候，可以非常快速的依据主键数值查询出该记录。从map的key值快速的查询出value值，这是map的主要应用。key对象在map中是不可以重复的，换个角度来理解，所有的key兑现的合集就是一个Set。



如上图所示：
       
        最原始的只有2中集合接口，Collection和Map 。Collection接口又有2个子接口List和Set，而在最终实现上，没有直接基于Collection接口的实现，List、Set和Map都有相应集合的实现类。（实际上，也是间接的实现，中间还有层抽象类）

        a、List接口实现包括ArrayList和LinkedList，还有传统的java1.1中实现的Vector，与Vector相关的还有一个Stack。ArrayList是可变容量数组，其特性和数组很接近；LinkedList是数据结构中的链表，链表的最大特性就是对元素的删除和添加操作效率非常高；Vector是传统的集合实现，已经不在推荐使用了，其实现完全可以用ArrayList和LinkedList代替。Stack是数据结构中栈的java实现，是一种后进现出的数据结构，因为其采用的是Vector来实现，所以也不被推荐使用。

        b、Set接口的实现包括HashSet和TreeSet。HashSet是数据散列，而TreeSet是一种排序的Set。
        c、Map接口的实现包括HashMap、TreeMap和HashTable。HashMap是最普通的Map实现，Map内元素成散列存取。TreeMap是排序                        Map。HashTable是传统的java实现，现在已经不推荐使用了，已经被HashMap代替。
        d、除了集合的四种接口Collection、Map、List、Set及其相关实现类外，集合框架中还有与其（collection分支）关系密切的一种特殊                   接口Iterator（迭代器），而Iterator又有一个子接口实现ListIterator。Iterator对象是由Collection接口对象产生的，而ListIterator则是由                 List接口对象产生的。Collection接口对象包含Collection子接口的所有实现（List和Set接口的所有实现），也就是说，Collection所                   有子接口对象都可以产生Iterator对象。List接口的实现类除了可以产生   Iterator 对象外，还可以产生ListIterator对象，那么Iterator有
              什么用呢？请看下一小节。

1.2 小谈一下Iterator（迭代器）
        集合是存放一组元素的，元素的存入和取出必然需要集合的实现类提供方法来支持。而不同的实现类提供的方法可能不同。如果开始设计的时候我们选择的集合是ArrayList，后来我们发现采用LinkedList更合理。但我们要改变实现的时候，所有元素访问的代码（原ArrayList访问方法）都要修改成新的设计中的元素访问方法（新的LinkedList访问方法）。如果能有这样一种思路，把“集合内元素的访问”和“实现采用的集合”分离开。把设计中可变因素和不可变因素分离开。这样一种设计思想必然会降低以后程序修改和维护的代价。Iterator就是这种设计思想的体现。从集合的实现中取得Iterator接口对象，然后通过Iterator对象遍历集合，然后采用Iterator接口的通用方法在集合中访问每一个元素，对于取得的元素执行相应的动作，这种通用的对于集合遍历的实现就是Iterator接口。
        因为其通用性的原因，Iterator的功能上是比较简单的，使用也有一些限制。比如，Iterator只能单项移动，Iterator接口提供的通用功能如下：
        （1）、从集合中获取Iterator接口对象方法：集合对象.Iterator（），返回集合对象的Iterator接口对象。
        （2）、Iterator对象.next()：从集合中取得下一个元素，返回object类型。
        （3）、Iterator对象.hasnext()：检查集合中是否还有下一个元素，返回布尔值。
        （4）、Iterator对象.remove()：从集合中删除最近获得对象元素，返回删除的对象。
Iterator是为遍历而设计的，能够从集合中取出元素和删除元素，但是没有添加元素的功能。集合遍历元素的顺序就是集合中元素存储的顺序。
        下面就来看看Iterator一个比较普遍的使用例子：
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

/**
* 功能：Iterator一个普通的小例子
* @author JackRui
* @date: 2009.03.31
*/
public class TestResultIter {

                int point;
                int no;
                String name;
                public TestResultIter(int point,int no,String name){
                        this.point = point;
                        this.no = no;
                        this.name = name;
                }
       
        public static void main(String[] args) {
                List coll = new ArrayList();
                TestResultIter jack = new TestResultIter(100,1,"jackrui");
                TestResultIter mary = new TestResultIter(90,2,"mary");
                TestResultIter terry = new TestResultIter(80,3,"terry");
                coll.add(jack);
                coll.add(mary);
                coll.add(terry);
                //定义一个迭代器，并指向装载数据的集合
                Iterator iter = coll.iterator();
                while(iter.hasNext()){
                        System.out.println(((TestResultIter)iter.next()).name);
                }
        }

}
       
这里值得一说的是，集合中的元素在放入的时候会“失去”类型，所以在取出的时候，要进行强制类型转化为当初的类型。

小记：在集合框架的体系结构中，还有一套公用工具类（Arrays和Collections）和2个比较接口（Comparable和Comparator），我们对集合或数组的元素进行排序的时候可以使用工具类中已经提供的方法（如，Arrays.sort()），对于比较的元素，要实现Comparable接口，或者单独设计一个比较算法类，该类实现Comparator接口。

                                                                                                1.3 Collection
Collection接口是Set接口和List接口的超类，所以Collection的特性都适用于Set和List接口，而Set和List接口在Collection的基础上。增加了新的特性和方法。下面是Collection接口的通用方法：
Boolean add(Object) 集合中加入一个对象，成功时返回true
Boolean addAll(Collection) 集合中加入另外一个集合对象
Int size() 集合内容纳元素的数量
Boolean isEmpty() 集合是否为空
Boolean contain(Object) 集合内是否有参数对象
Iterator iterator() 产生一个迭代器
Object[] toArray() 返回一个包含所有元素的对象数组
Object[] toArray(Object[]) 把所有元素放入对象数组中
Boolean remove(Object) 从集合中删除对象
Boolean removeAll(Collection) 清空指定集合
Boolean contaunsAll(Collection) 判断集合内是否包含子集
Boolean retainAll(Collection) 删除子集合不包含的元素
Void clear() 清空集合


Collection中虽然提供了一些删除的方法，如remove、removeall等，但是没有提供get（）取出元素的方法，因为，Collection包括了可以按照顺序取的List接口外，还包含了无序的Set接口，因为无序所以无法按照顺序去取元素的get（）操作。虽然没有实现get方法，但是对于
Collection的遍历还是提供了通用的方法，推荐使用Iterator迭代器，而Iterator已经提供了remove和get方法。
               
  1.3.1  List
        List 是有一定顺序的集合（也称为Sequence序列），它与Set的区别是List中的元素可以重复，Set是无序的。
        List对于Collection的主要增强功能有2点：
        首先，因为List元素是有序性，所以每个元素都有一个Index值，与该索引值相关增加了一些方法：添加元素的时候，可以在指定集合位置添加元素。同样，删除的时候也可以删除指定位置的元素。当然，也可以按照其索引值来取出元素。
        其次，可以通过List取得ListIterator来访问List，ListIterator接口是Iterator接口的子类，其增强的地方是Iterator只能单项遍历，而ListIterator可以是双向的，另外，ListIterator有增加元素的功能，而Iterator没有此功能。
     
       
List增加的方法：

Void (int index,Object element) 在指定索引位置添加元素
Object get(int index) 在List指定位置添加元素对象
Int indexOf(Object o) 在List中查询元素的索引值，如果元素不存在返回-1
Int lastIndexOf(Object o) List中如果存在多个重复的元素，则indexOf返回第一个匹配元素的index，lastIndexOf（Object o）返回最后一个匹配的元素的index
ListIterator ListIterator() 返回ListIterator迭代器
Object remove(int index) 删除集合中指定位置的元素，并把该元素返回
Object set(int index,Object element) 重新设置集合中该位置的元素


ListIterator接口除了Iterator接口已经具备的hasNext（）、next（）、remove（）方法之外，还增加了下面的一些主要方法：

ListIterator接口方法 方法说明
Void add（int index，Object element） 在指定的索引位置添加元素
Object get(int index) 在List指定位置取得元素对象
Void add（Object o） 向集合中添加元素
Boolean hasPrevious（） 判断集合中是否有前驱元素
Int nextIndex（） 取得集合中下一个元素的index值
Object Previous（） 取得集合中当前位置的前驱元素
Int PreviousIndex（） 取得集合中后继元素的Index值
Void set（Object o） 更新集合当前位置元素

1.3.1.1  ArrayList

        ArrayList 集合的存取方式和数组操作很类似，可以按照index顺序来存取集合中的元素，但是还是建议采用更通用的迭代器来进行ArrayList的遍历。
        ArrayList与数组最大的区别就是它是可变数组，在初始化ArrayList集合的时候，可以指定一个初始化容量（Capacity 集合中可容纳元素的数量），不指定的时候，系统会指定一个默认的容量值。当我们向ArrayList集合添加元素的时候，实际上是存放元素数量（size）在不断的增加，当容量不变，当数量增长到初始容量大小的时候，因为没有空间导致元素添加阻塞，这时候该集合的容量会按照一定增长策略自动增长，容量增长后，可以继续向集合中添加元素。可变数组是ArrayList的优点，但从另外一个角度考虑，容量的增长是需要付出额外的代价的，所以在性能上有所损失。性能问题的一种解决思路是我们可以在向集合添加大量元素之前，根据欲添加元素的数量，预先扩充容量，采用的是ensureCapacity方法。
        ArrayList是一种线性表，在内存中是连续存储的，适合于元素的随机存取。添加和删除操作是需要依据添加的位置来定，如果在ArrayList最后元素后面添加和删除元素，在性能方面还算好，但是如果是在ArrayList中间添加和删除元素的话，代价就会很大。因为，ArrayList需要维护整个集合元素的顺序存储，所以需要处理欲添加和删除元素位置之后的所有元素。
        ArrayList的实现不是线程安全的。也就是说，如果有多个线程同时操作ArrayList集合对象，而且其中至少有一个线程的操作涉及到集合对象中元素的修改（添加和删除），则该线程内对集合对象操作的方法需要实现同步。这也是ArrayList与Vector的主要区别。在新的集合框架的实现上，基于性能的考虑，大部分的集合设计都是线程不安全的。如果有同步需求，在用户自己的实现中可以实现同步，实现的方法有2种：
        1、在操作集合对象的方法上使用synchronized关键字。
        2、如果方法不可修改，则可在定义集合的时候，定义同步化的集合对象（采用Collections工具类的方法），类似：
                List list = Collection.synchronizedList(new ArrayList(.....));
        （此处深入说明下，在采用Iterator遍历集合的时候，如果有其他线程修改了集合（添加或删除操作），那么Iterator的处理会中止并抛出ConcurrentModificationException异常,这是集合处理中的Fail-safe特性）
ArrayList提供的方法中，除了Collection和List的公用方法外，又加入了一些新的方法。
 
ArrayList（int initialCapacity） 构造器方法增加了集合初始化的最小容量
Void ensureCapacity(int minCapacity) 预扩充ArrayList的容量
Void trimToSize() 把集合的Capacity缩小到Size的大小


下面做一个ArrayList小例子：
       
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
* @功能：ArrayList的应用小例子
* @author JackRui
* @时间：2009.03.31
*/
public class ArrayListDemo {

        public static void main(String[] args) {
        //利用ArrayList本身的特性
                System.out.println("利用ArrayList本身的特性");
                ArrayList list = new ArrayList();
                list.add("aaa");
                list.add("bbb");
                list.add("ccc");
                list.remove("bbb");
                list.add("ddd");
                for (int i=0,lsize=list.size();i<lsize;i++){
                        System.out.println(list.get(i));
                }
        //利用Iterator遍历
                System.out.println("利用Iterator遍历");
                Collection clist = new ArrayList();
                clist.addAll(list);//添加元素不能采用Iterator接口
                Iterator iter = clist.iterator();
                while(iter.hasNext()){
                        String s = (String)iter.next();
                        if(s.equals("ddd")){
                                iter.remove();//可以通过Iterator接口对元素进行删除
                        }else{
                                System.out.println(s);
                        }
                }
        //利用ListIterator遍历       
                System.out.println("利用ListIterator遍历");
                List list2 = new ArrayList();
                ListIterator lit = list2.listIterator();
                if(!lit.hasNext()){
                        lit.add("haha");//可以通过ListIterator接口进行集合元素的添加
                        lit.previous();
                        System.out.println(lit.next());
                }
                   
        }

}
        运行结果如下：
利用ArrayList本身的特性
aaa
ccc
ddd
利用Iterator遍历
aaa
ccc
利用ListIterator遍历
haha


解析：3种方法中，第一种方法不通用，不建议使用。第2种方法最通用，但仅支持单向遍历，而且对象的添加需要分开实现。第3种方法可以双向遍历，而且可以直接使用ListIterator接口来添加对象。
问题：为什么next取得元素后，可以直接System.ou.print呢？而在String s = (String)iter.next();的时候必须进行强制类型转化呢？

1.3.1.2  LinkedList
        linkedList 是功能最强大，使用最广泛的java集合实现类。
        linkedList是数据结构中的链表的java实现，元素在linkedList 中的存储是一个元素接着一个元素串联起来，通过每个元素维护其前驱或后继节点的连接。linkedList的线性化特征已经很弱了，因为它不需要顺序存储，也正是这个原因，如果在需要随机存取的场合是不太适用linkedList的，但是在添加和删除元素的方面上，linkedList的性能还是很高的。linkedList容纳的元素的数量也是自动动态增长的。
        linkedList最主要的功能方面的增强是在List的头部或者尾部进行添加、删除和取得元素，它直接提供了这些方法的实现。所以linkedList可以非常方便的实现我们数据结构中常见的Stack（栈）、queue（队列）等。
        linkedList增强功能的方法如下：

Void addFirst(Object o) 在List的头部添加对象
Void addLast(Object o) 在List尾部添加对象
Object getFirst() 从List头部取得对象
Object getLast() 从List尾部取得对象
Object removeFirst() 从List头部删除对象
Object removeLast() 从List尾部删除对象


下面写一个linkedList的例子：
        这个例子是用LinkedList设计一个测试队列，这也可以作为我们自己的类库来使用。（队列的特性是（FIFO）先进现出，要注意的是，当取队列的元素的时候要判断队列是否为空，所以用到了isEmpty方法）

        import java.util.LinkedList;

/**
* @功能：用LinkedList设计一个测试队列
* @author JackRui
* @时间：2009.03.31
*
*/
public class QueueDemo {
       
        private LinkedList list = new LinkedList();
       
        public void put(Object o){
                list.addFirst(o);
               
        }
       
        public Object get(){
                return list.removeLast();
        }
       
        public boolean isEmpty(){
                return list.isEmpty();
        }
       
       
        public static void main(String[] args) {
               
                QueueDemo queue = new QueueDemo();
                queue.put("one");
                queue.put("two");
               
                while(!queue.isEmpty()){
                        System.out.println(queue.get());
                }
        }
}

  执行结果如下：
one
two

        解析：实现了队列的特性 先进先出，先进的顺序是one two 出来也是one  two
        问题：如何将队列改成栈？如何增加判断队列的长度方法？该实现中是否可以采用queue继承LinkedList来设计呢？
        比较：ArrayList和LinkedList的比较：ArrayList是顺序存储，而LinkedList是链式存储；ArrayList适合随机查找的场合，按照索引值取元素、设置元素等操作性能高，但是插入和删除元素的性能比较差，尤其是在集合中间做插入和删除操作，而LinkedList插入和删除的性能高，不适合随机查询。

          1.3.2  Set
        Set接口是collection接口的另一个子接口。它与list的区别是Set集合内存放的元素都是唯一的，不可以重复的。而且，向set里存放的元素不是按照原来的顺序存储的。
        set主要有2种集合实现，一个是HashSet，一个是TreeSet，既然都属于Set接口，所以，这两种集合内容纳的对象也是不可以重复的。
        HashSet 的特征在于其内对象的散列存取，即采用哈希技术，每个对象利用Hashcode（）方法算出一个唯一的hash值，然后在根据该hash值把各个对象尽可能均匀分布到集合中。当读取对象的时候，同样先计算出对象的hash值，然后根据hash值快速到集合中相应的位置（可以理解为hash值默认的实现是与存储位置相关的数据）取出对象元素。自然，hashSet的优点在于快速定位元素。
        HashSet内存放的对象有2个要求，除了equals方法判断元素时候重复外，还要使用hashCode（）方法来快速定位元素，在需要的时候，这2中方法都要覆盖。
        TreeSet虽然是存入的顺序和存储的顺序是不一样的，但是存储是按照排序存储的，也就是说在存储的时候是用到了Arrays中提到的比较接口Comparable和Comparator。
        下面是一个HashSet和TreeSet的例子：

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
* @功能：实现一个HashSet和TreeSet的例子
* @author JackRui
* @时间：2009.03.31
*/
public class SetDemo {
       
        private static void printCol(Collection coll){
                Iterator iter = coll.iterator();
                while(iter.hasNext()){
                        System.out.println(iter.next());
                }
        }
       
        public static void main(String[] args) {
                Collection coll = new ArrayList();
                coll.add("c");
                coll.add("a");
                coll.add("b");
                coll.add("a");
               
                Set set1 = new HashSet();
                Set set2 = new TreeSet();
               
                set1.addAll(coll);
                set2.addAll(coll);
               
                System.out.println("现在开始打印HashSet的内容： ");
                printCol(set1);
                System.out.println("现在开始打印TreeSet的内容： ");
                printCol(set2);
               

        }

}
              
      执行结果如下：
现在开始打印HashSet的内容：
a
c
b
现在开始打印TreeSet的内容：
a
b
c


代码解释：从结果看到，无论是HashSet还是TreeSet，都没有重复的值（像Set中重复存储对象是可以执行的，但只能存储一次罢了，这也是Set的基本特性。）  HashSet区别的地方是对象是散列开的，具体体现在输出上。我们输入的顺序是cab，经过HashSet存储后输出的顺序变成acb了，而TreeSet是有序的。



1.4  Map
        Map是不同于Collection的另外一种集合接口，说到Map的适用范围，我们先来看看一个很平常的选择数据的例子。
        我们在选择数据的时候，我们选择思路的依据是什么呢？比如，想从班级里选择一个学生对象，班级中按照学生报道的先来后到顺序排成学号，学号的同时代表了学生的序号（班级里学生的索引值），学生还有姓名信息等，我们选择的信息可能有这么几种：
       
     （1）、每次都取出班级最后来的学生-----栈的思路
     （2）、每次都取出班级最先来的学生-----队列的思路
     （3）、按照每个学生的学号来查找学生----List的思路，如果学生的学号是连续的，则是ArrayList的思路，如果每个学生都是通过其他学生关联查询出来的（比如按照座位次序），则是LinkedList思路。
     （4）、如果班级里不允许重名的学生存在，这是set思路。
     （5）、如果想通过学生的姓名查询出该学生来，这就是map思路。

        Map内存储的是键/值对这样以成对的对象组（可以把一组对象当成一个元素），通过“键”对象来查询“值”对象，这个概念类似于数据库中的表的查询，表经常会设置主键，主键对于每条记录来说都是唯一的，所以，只要能快速的找到主键，就可以快速的定位到一条记录，从而取出这条记录，这在数据库中使用的方法是索引。在Map中，键（key）值也是唯一的，我们通过一些方法快速的找到key，而key对象和value对象是关联在一起的，自然也就找到了value对象，从而快速取得value值。
        Map接口有2个实现，HashMap和TreeMap，HashMap中key/value对的存放和查询是采用Hash算法，每个key对象都对应唯一的一个hash值，根据该hash值，可以快速的定位key对象，进行快速定位到value对象。在插入元素的时候，如果key已经存在，则替换原来的value对象。TreeMap中键/值对是排序（按照key排序）存储的。

下面写一个HashMap和TreeMap的小例子吧：

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

/**
* @功能：实现一个HashMap和TreeMap的小例子
* @author JackRui
* @时间：2009.03.31
*
*/
public class MapDemo {

        int point;
        int no;
        String name;
       
        public MapDemo(int point,int no,String name){
                this.point = point;
                this.no = no;
                this.name = name;
               
        }
       
        private static void printCol(Collection coll){
                Iterator iter = coll.iterator();
                while(iter.hasNext()){
                       
                        System.out.println(iter.next());
                }       
        }
       
       
        public static void main(String[] args) {
                HashMap map1 = new HashMap();
                map1.put("Zrjack", new MapDemo(100,1,"ZrJackRui"));
                map1.put("mary", new MapDemo(80,2,"mary"));
                map1.put("terry", new MapDemo(90,3,"terry"));
               
                MapDemo mapdemo = (MapDemo)map1.get("Zrjack");
                System.out.println("jack's result is "+mapdemo.point);
               
                Set set1 = map1.keySet();
                printCol(set1);
               
               
                TreeMap map2 = new TreeMap();
                map2.put("Zrjack", new MapDemo(100,1,"ZrJackRui"));
                map2.put("mary", new MapDemo(80,2,"mary"));
                map2.put("terry", new MapDemo(90,3,"terry"));
               
                MapDemo mapdemo1 = (MapDemo)map1.get("Zrjack");
                System.out.println("jack's result is "+mapdemo1.point);
               
                Set set2 = map2.keySet();
                printCol(set2);

        }

}
        执行结果：

jack's result is 100
terry
Zrjack
mary
jack's result is 100
Zrjack
mary
terry

        结果分析：程序分别用了HashMap和TreeMap来存储数据，在TreeMap的时候，进行了排序（按首字母的大小进行排序），值得注意的地方是，排序的时候，大写字母永远都排在小写字母前面，如A 要排在a的前面。

        HashMap和HashTable  的比较：HashTable是jiava传统的实现，其工作原理和功能和HashMap和接近，但是已经不推荐使用了，HashTable是线程安全的，HashMap不是线程安全的。从性能的角度上考虑，HashMap要比HashTable要好。
   









   
                       1.5 集合公用工具类&集合异常类
1.5.1 Collection 公用工具
        Collection 类是类似于Arrays类的公用工具类，Arrays提供了供数组使用的公用方法，而Collection提供了一些static方法供集合类使用或操作集合类。
        Collection 中提供的方法比较多，这里说明比较常用的方法

Collection类的公用方法
Enumeration enumeration(Collection c) 返回传统的一个遍历接口Enumeration
Object max(Collection c) 返回集合中最大元素，需要考虑比较接口的实现
Object max(Collection c,Comparator comp) Max算法采用Comparator比较算法
Object min(Collection c) 返回集合中最小元素
Void reverse(Collection c) 把集合中的元素顺序反转
Void copy(List desc,List src) Src集合中的元素复制到desc集合
Void fill(List list, Object o) 填充list集合，填充的元素为o
Void sort(List list) 对一种list做排序
Int binarySearch(List list,Object key) 对排序后的集合list进行查询元素操作
List synchronizedList(List list) 返回线程安全的List，同步方法还有Map，Set等的实现
       
        在这些工具方法中，sort（）、binarySearch（）以及reverse（）在排序和查找中比较常用，再次强调的是，要使用这些方法的时候，一是集合中的元素要实现比较接口，二是一定要先比较，再查询。
        Enumeratruon 是java1中提供的遍历集合的接口，已经不在推荐使用了。但是在一些实现或者实际应用中，可能还会看到Enumeratruon的使用，虽然我们推荐使用Iterator接口，但是遇到Enumeratruon接口的时候，也要能理解，Enumeratruon提供的接口方法和Iterator很相似。














1.5.2 集合处理中的常见异常
        集合处理中的常用异常表如下：


ClassCastException 从集合中取得元素对象在进行类型转换的时候类型不匹配
UnsupportedOperationException 当底层实现没有实现上层的相关方法的时候由collection抛出异常。Collection接口（或其他集合超类）中的一些函数在java doc中是标明“可有可无（Optional）”的函数，这些函数在底层的一些具体实现中，有的实现了，有的没有实现，当我们调用底层实现集合类的这些有实现的方法时就会抛出该异常。
ConcurrentModificationException 当采用Iterator遍历集合时，如果此集合中的元素被改变则Iterator遍历抛出此异常
IndexOutOfBoundsException 集合中元素引用的索引值超出界限（<0或>size（））
NoSuchElementException LinkedList中getLast，getFirst等方法取元素的时候List为空。


       以上异常都是RuntimeException的子类，在编程的时候可以不处理该异常，如果出现问题，在程序运行期间由jvm抛出。

下面写一个关于ConcurrentModificationException异常的小例子

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;

/**
* @功能：一个关于ConcurrentModificationException异常的小例子
* @author JackRui
* @时间：2009.03.31
*/
public class CollExceptionDemo {

        public static void main(String[] args) {
                Collection coll = new LinkedList();
                Iterator iter = coll.iterator();
                coll.add("a");
                String s = (String)iter.next();
               
        }

}

执行结果如下：
        java.util.ConcurrentModificationException
       。。。

    1.5 .1 泛型
     java1.5 中增加了泛型的概念，可以更方便的定义集合的数据类型和对集合中的数据进行访问，关于泛型的概念需要单独讲解，就不在这里说了。

       

评论

2 楼 gaok1 2012-05-11  

很详细，以后忘记时候好好翻出来复习复习

1 楼 robin35java 2011-04-21  

好文章，讲的很详细，关键是还有例子，能加深对collection的理解。