Java list 集合类.doc

Java list 集合类在JDK API中专门设计了一组类，这组类的功能就是实现各种各样方式的数据存储，这样一组专门用来存储其它对象的类，一般被称为对象容器类，简称容器类，这组类和接口的设计结构也被统称为集合框架(Collection Framework)。 这组类和接口都包含在java.util包中。 为了使整个集合框架中的类便于使用，在设计集合框架时大量的使用接口，实际实现的功能类实现对应的接口，这样可以保证各个集合类的使用方式保持统一。在集合框架中，提供的存储方式共有两种：1、按照索引值操作数据在这种存储方式中，为每个存储的数据设定一个索引值，存储在容器中的第一个元素索引值是0，第二个索引值是1，依次类推。在操作数据时按照索引值操作对应的数据，实现这种方式的集合类都实现java.util.Collection接口。2、按照名称操作数据在这种存储方式中，为每个存储的数据设定一个名称(任意非null的对象都可以作为名称)，以后按照该名称操作该数据，要求名称不能重复，每个名称对应唯一的一个值。这种存储数据的方式也称作名称-数值对，也就是名值对存储。实现这种方式的几个类都实现java.util.Map接口。这里“按照索引值操作数据”的存储方式，又按照容器内部是否能够存储重复的元素，划分成两类：1、允许存储重复元素。这种存储方式中，所有的类都实现了java.util.List接口。2、不允许存储重复元素。这种存储方式中，所有的类都实现了java.util.Set接口。这样，集合框架中的类就分成了三大类：1、List系列该系列中的类按照索引值来操作数据，允许存放重复的元素。2、Set系列该系列中的类按照索引值来操作数据，不允许存放重复的元素。3、Map系列该系列中的类按照名称来操作数据，名称不允许重复，值可以重复，一个名称对应一个唯一的值。而在数据结构中，实现数据的存储又可以使用不同的数据结构类型进行存储，例如数组、链表、栈、队列和树等，则以上三类集合框架可以使用不同的数据结构类进行实现，使用每种数据结构则具备该中数据结构的特点。例如使用数组则访问速度快，使用链表则便于动态插入和删除等，这样就造成了集合框架的复杂性。另外，在将对象存储到集合类中，为了加快存储的速度，要求被存储对象的类中必须覆盖equals方法和hashCode方法。对于这些集合类，下面按照以上三个系列的顺序一一进行说明。9.6.3.1 List系列List系列的类均实现List接口，大部分的类都以List作为类名的后缀，也有部分该体系中的类命名比较特殊。 该系列中的类，比较常见的有ArrayList和LinkedList两个。其中ArrayList是以数组为基础实现的List，而LinkedList则是以链表为基础实现的List，ArrayList拥有数组的优点，而LinkedList拥有链表的优点。由于该体系中的类均实现List接口，所以在这些类的内部，相同的功能方法声明是保持一致的，下面进行一一介绍：a、add方法 boolean add(Object o)该方法的作用是追加对象o到已有容器的末尾。另外一个add方法： void add(int index, Object element)该方法的作用是将对象element插入到容器中索引值为index的位置，原来位于该位置的对象以及后续的内容将依次向后移动。b、addAll方法 boolean addAll(Collection c)该方法的作用是将容器对象c中的每个元素依次添加到当前容器的末尾。另外一个addAll方法： boolean addAll(int index, Collection c)该方法的作用是将容器对象c中的第一个元素插入到当前容器中索引值为index的位置，第二个元素插入到当前容器中索引值为index+1的位置，依次类推。而当前容器中原来位于index以及index索引值以后的元素则依次向后移动。c、get方法 Object get(int index)该方法的作用是返回当前容器对象中索引值为index的元素的内容。d、indexOf方法 int indexOf(Object o)该方法的作用是查找当前容器中是否存在对象o，如果存在则返回该对象第一次出现位置的索引值，如果不存在则返回-1。另外一个方法lastIndexOf则是从末尾向前查找，返回从末尾向前第一次出现位置的索引值，如果不存在则返回-1。e、remove方法 Object remove(int index)该方法的作用是删除索引值为index的对象的内容，如果删除成功则返回被删除对象的内容。另外一个remove方法： boolean remove(Object o)该方法的作用是删除对象内容为o的元素，如果相同的对象有多个，则只删除索引值小的对象。如果删除成功则返回true，否则返回false。无论使用哪一个remove方法，类内部都自动移动将被删除位置后续的所有元素向前移动，保证索引值的连续性。f、set方法 Object set(int index, Object element)该方法的作用是修改索引值为index的内容，将原来的内容修改成对象element的内容。g、size方法 int size()该方法的作用是返回当前容器中已经存储的有效元素的个数。h、toArray方法 Object toArray()该方法的作用是将当前容器中的元素按照顺序转换成一个Object数组。下面是一个简单的以ArrayList类为基础实现的List系列中类基本使用的示例，代码如下： import java.util.*;/* * 以ArrayList类为基础演示List系列类的基本使用 */public class ArrayListUse public static void main(String args) /容器对象的初始化 List list = new ArrayList(); /添加数据 list.add(1); list.add(2); list.add(3); list.add(1); list.add(1); /插入数据 list.add(1,12); /修改数据 list.set(2, a); /删除数据 list.remove(1); /遍历 int size = list.size(); /获得有效个数 /循环有效索引值 for(int i = 0;i size;i+) System.out.println(String)list.get(i); 该程序的运行结果为：12a311一般大家都知道ArrayList和LinkedList的大致区别：1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 ArrayList 和LinkedList是两个集合类，用于存储一系列的对象引用（references）。例如我们可以用ArrayList来存储一系列的String 或者Integer.那么 ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？一、时间复杂度首 先一点关键的是，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时（random access），它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对 LinkedList而言，访问列表中的某个指定元素没有更快的方法了。假 设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来 进行二分查找（binary search），比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：Java代码package com.mangocity.test；import java.util.LinkedList；import java.util.List；import java.util.Random；import java.util.ArrayList；import java.util.Arrays；import java.util.Collections；public class TestList public static final int N=50000；public static List values；static Integer vals=new IntegerN；Random r=new Random（）；for（int i=0，currval=0；iN；i+） vals=new Integer（currval）；currval+=r.nextInt（100）+1；values=Arrays.asList（vals）；static long timeList（List lst） long start=System.currentTimeMillis（）；for（int i=0；iN；i+） int index=Collections.binarySearch（lst， values.get（i）；if（index！=i）System.out.println（*错误*）； return System.currentTimeMillis（）-start； public static void main（String args） System.out.println（ArrayList消耗时间：+timeList（new ArrayList（values）；System.out.println（LinkedList消耗时间：+timeList（new LinkedList（values）；我得到的输出是：ArrayList消耗时间：15 LinkedList消耗时间：2596这 个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList.二分查找法 使用的随机访问（random access）策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例 的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。这 是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些 算法在LinkedList中实现时效率更高。比方说，利用 Collections.reverse方法对列表进行反转时，其性能就要好些。看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：Java代码package com.mangocity.test；import java.util.*；public class ListDemo static final int N=50000；static long timeList（List list） long start=System.currentTimeMillis（）；Object o = new Object（）；for（int i=0；iN；i+）list.add（0， o）；return System.currentTimeMillis（）-start； public static void main（String args） System.out.println（ArrayList耗时：+timeList（new ArrayList（）；System.out.println（LinkedList耗时：+timeList（new LinkedList（）；这时我的输出结果是：ArrayList耗时：2463 LinkedList耗时：15这 和前面一个例子的结果截然相反，当一个元素被加到 ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只 是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元 素的开销是与ArrayList的大小成比例的。二、空间复杂度 在LinkedList中有一个私有的内部类，定义如下：private static class Entry Object element；Entry next；Entry previous；每 个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的 LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将 有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。ArrayList 使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按如下公式获得：新容量=（旧容量*3）/2+1，也就是说每一次 容量大概会增长50%.这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由 ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将 会导致性能急剧下降。如果我们知道一个ArrayList 将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。三、总结ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：1. 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。3.LinkedList不支持高效的随机元素访问。4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。在List系列中，还包含了Stack(栈)类和Vector(向量)类，Stack类除了实现List系列的功能以外，还实现了栈的结构，主要实现了出栈的pop方法和入栈的push方法。构造方法 ： public Stack() 创建一个空 Stack。方法： 1. public push （item ） 把项 压入栈顶。其作用与 addElement (item ) 相同。返回： item 参数 ；2. public pop () 移除栈顶对象，并作为函数的值 返回该对象。返回：栈顶对象（Vector 对象的中的最后一项）。抛出异常 ： EmptyStackException 如果堆栈式空的 。3. public peek() 查看栈顶对象而不移除它。 返回：栈顶对象（Vector 对象的中的最后一项）。抛出异常 ： EmptyStackException 如果堆栈式空的 。4. public boolean empty （测试堆栈是否为空。） 当且仅当堆栈中不含任何项时 返回 true，否则 返回 false.5. public int search (object o) 返回对象在堆栈中位置， 以 1 为基数， 如果对象 是栈中的一项，该方法返回距离栈顶最近的出现位置到栈顶的距离；栈中最上端项的距离为。 Vector 可实现自动增长的对象数组。 java.util.vector提供了向量类(vector)以实现类似动态数组的功能。在Java语言中没有指针的概念，但如果正确灵活地使用指针又确实可以大大提高程序的质量。比如在c,c+中所谓的“动态数组”一般都由指针来实现。为了弥补这个缺点，Java提供了丰富的类库来方便编程者使用，vector类便是其中之一。事实上，灵活使用数组也可以完成向量类的功能，但向量类中提供大量的方法大大方便了用户的使用。 创建了一个向量类的对象后，可以往其中随意插入不同类的对象，即不需顾及类型也不需预先选定向量的容量，并可以方便地进行查找。对于预先不知或者不愿预先定义数组大小，并且需要频繁地进行查找，插入，删除工作的情况。可以考虑使用向量类。 向量类提供了三种构造方法： public vector() public vector(int initialcapacity,int capacityIncrement) public vector(int initialcapacity) 使用第一种方法系统会自动对向量进行管理，若使用后两种方法。则系统将根据参数，initialcapacity设定向量对象的容量（即向量对象可存储数据的大小），当真正存放的数据个数超过容量时。系统会扩充向量对象存储容量。 参数capacityincrement给定了每次扩充的扩充值。当capacityincrement为0的时候，则没次扩充一倍，利用这个功能可以优化存储。在Vector类中提供了各种方法方便用户的使用： 插入功能： （1）public final synchronized void adddElement(Object obj) 将obj插入向量的尾部。obj可以是任何类型的对象。对同一个向量对象，亦可以在其中插入不同类的对象。但插入的应是对象而不是数值，所以插入数值时要注意将数组转换成相应的对象。 例如：要插入整数1时，不要直接调用v1.addElement(1),正确的方法为： Vector v1 = new Vector(); Integer integer1 = new Integer(1); v1.addElement(integer1); (2)public final syn