JAVA程序设计笔试题库及答案

JAVA基础题库

1、作用域public,private,protected,以及不写时的区别

注：不写时关键字默认为friendly

作用域 当前类 同一package 子孙类 其他package

public √ √ √ √

protected √ √ √ ×

friendly √ √ × ×

private √ × × ×

2、Anonymous Inner Class (匿名内部类)是否可以extends(继承)其它类，是否可以implements(实现)interface(接口)

答：匿名的内部类是没有名字 的内部类。不能extends(继承)其 它类，但一个内部类可以作为一个接口，由另一个内部类实现

3、&和&&的区别。

答：&和&&都可以用作逻辑与的运算符，表示逻辑与（and），当运算符两边的表达式的结果都为true时，整个运算结果才为true，否则，只要有一方为false，则结果为false。

&&还具有短路的功能，即如果第一个表达式为false，则不再计算第二个表达式，例如，对于if(str != null && !str.equals(“”))表达式，当str为null时，后面的表达式不会执行，所以不会出现NullPointerException如果将&&改为&，则会抛出NullPointerException异常。If(x==33 & ++y>0) y会增长，If(x==33 && ++y>0)不会增长

&还可以用作位运算符，当&操作符两边的表达式不是boolean类型时，&表示按位与操作，我们通常使用0x0f来与一个整数进行&运算，来获取该整数的最低4个bit位，例如，0x31 & 0x0f的结果为0x01。

4、Static Nested Class 和 Inner Class的不同

Nested Class 一般是C++的说法，Inner Class 一般是JAVA的说法。

Nested class分为静态Static nested class 的和非静态的 inner class,

静态的Static nested class是不可以直接调用它的外部类enclosing class的，但是可以通过外部类的引用来调用，就像你在一个类中写了main方法一样。

非静态类inner class 可以自由的引用外部类的属性和方法，但是它与一个实例绑定在了以其，不可以定义静态的属性、方法 。

Inner Class（内部类）定义在类中的类。

Nested Class（嵌套类）是静态（static）内部类。1. 要创建嵌套类的对象，并不需要其外围类的对象。 2. 不能从嵌套类的对象中访问非静态的外围类对象。

Anonymous Inner Class （匿名内部类）匿名的内部类是没有名字的内部类。

匿名的内部类不能extends（继承）其它类，但一个内部类可以作为一个接口，由另一个内部类实现。

嵌套类可以作为接口的内部类。正常情况下，你不能在接口内部放置任何代码，但嵌套类可以作为接口的一部分，因为它是static 的。只是将嵌套类置于接口的命名空间内，这并不违反接口的规则。

静态方法是不能继承的，因为它是静态的，所谓静态当然是时间和空间的静止喽……所以任何人都别想改变他。

但是它不介意有人和它叫一样的名字，所以子类是可以cover的，但是其实这

样会出来两个函数，一个父类的一个子类的，各管各的。

然后final是java里面定义的，不能被重载的函数。

java里面的函数如果没有特别标识，只要在子类中定义了一个同名的函数，那么父类的函数就被重载掉了。如果new一个子类的对象给父类再调用这个函数，就是调用子类的了。只有new的是父类的调的才是父类的。

java里面没有virtual的说法，因为不是final或static就是virtual的。

abstract是虚函数，自然不可能是final的，同时如上所说，static是不能被重载只能被覆盖的，所以也不可以是abstract的

内部类被继承,由于内部类有一个指向外围类对象的秘密引用，所以在继承内部类的时候，该秘密引用必须被初始化。解决方法是enclosingClassReference.super();语法，看一下代码：

class Outer

...{

class Inner

...{

}

}

class AnoClass extends Outer.Inner

...{

AnoClass (Outer wi)

...{

wi.super();

}

}

匿名类（Anonymous Class）

　　当一个内部类的类声名只是在创建此类对象时用了一次，而且要产生的新类需继承于一个已有的父类或实现一个接口，才能考虑用匿名类，由于匿名类本身无名，因此它也就不存在构造方法，它需要显示地调用一个无参的父类的构造方法，并且重写父类的方法。

。。。。。。。。。。。。

f.addMouseMotionListener(new MouseMotionAdapter(){ //匿名类开始

　　　　　　　public void mouseDragged(MouseEvent e){

　　　　　　　　String s="Mouse dragging: x="+e.getX()+"Y="+e.getY();

　　　　　　　　tf.setText(s); }

　　　　　　} ); //匿名类结束

　　存在它的原因是:

　　1.一个内部类的对象能够访问创建它的对象的实现，包括私有数据。即内部类实例对包含它的哪个类的实例来说，是特权的。

　　2.对于同一个包中的其他类来说,内部类能够隐藏起来,换句话说，内部类不管方法的可见性如何，那怕是public，除了包容类，其他类都无法使用它。

　　3.匿名内部类可以很方便的定义回调。

　　4.使用内部类可以非常方便的编写事件驱动程序。

其实它真正的目的仅仅为了定义回调－－进一步就是事件驱动。

　在使用匿名内部类时，要记住以下几个原则：

　　?匿名内部类不能有构造方法。

　　?匿名内部类不能定义任何静态成员、方法和类。

　　?匿名内部类不能是public,protected,private,static。

　　?只能创建匿名内部类的一个实例。

?一个匿名内部类一定是在new的后面，用其隐含实现一个接口或实现一个类。

　　?因匿名内部类为局部内部类，所以局部内部类的所有限制都对其生效。

匿名类和内部类中的中的this :

有时候，我们

会用到一些内部类和匿名类。当在匿名类中用this时，这个this则指的是匿名类或内部类本身。 这时如果我们要使用外部类的方法和变量的话，则应该加上外部类的类名。

5、ASCII，unicode和UTF-8，UTF－16，gbk，gb2312的区别与不同。

1.ASCII(American Standard Code for Information Interchange)码，是一种字符集。美国标准信息交换代码是由美国国家标准学会(American National Standard Institute , ANSI )制定的，标准的单字节字符编码方案，用于基于文本的数据。起始于50年代后期，在1967年定案。它最初是美国国家标准， 供不同计算机在相互通信时用作共同遵守的西文字符编码标准，它已被国际标准化组织（International Organization for Standardization, ISO）定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母。ASCII 码使用指定的 7 位或 8 位二进制数组合来表示 128 或 256 种可能的字符。标准 ASCII 码也叫基础ASCII码，使用 7 位二进制数来表示所有的大写和小写字母，数字 0 到 9、标点符号， 以及在美式英语中使用的特殊控制字符。其中：

0～31及127(共33个)是控制字符或通讯专用字符（其余为可显示字符），如控制符：LF（换行）、CR（回车）、FF（换页）、DEL（删除）、BS（退格)、BEL（振铃）等；通讯专用字 符：SOH（文头）、EOT（文尾）、ACK（确认）等；ASCII值为 8、9、10 和 13 分别转换为退格、制表、换行和回车字符。它们并没有特定的图形显示，但会依不同的应用程序，而对文本显示有不同的影响。

32～126(共95个) 是字符(32sp是空格），其中48～57为0到9十个阿拉伯数字；

　　65～90为26个大写英文字母，97～122号为26个小写英文字母，其余为一些标点符号、运算符号等。

同时还要注意，在标准ASCII中，其最高位(b7)用作奇偶校验位。所谓奇偶校验，是指在代码传送过程中用来检验是否出现错误的一种方法，一 般分奇校验和偶校验两种。奇校验规定：正确的代码一个字节中1的个数必须是奇数，若非奇数，则在最高位b7添1；偶校验规定：正确的代码一个字节中1的个 数必须是偶数，若非偶数，则在最高位b7添1。

2.UNICODE（Universal Multiple-Octet Coded Character Set)字符集

Unicode（统一码、万国码、单一 码）是一种在计算机上使用的字符编码。它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。

unicode有两种方式：UCS-2,UCS-4,顾名思义，是两个字节和4个字节。

具体的可以google和百度。总的来讲，计算机前期，一般是ASCII，现在基于全球一体化，基本都用unicode。

－－－－－－－－－－－－－－－－－－－－－－－－

－－－－－

字符编码

1.Gbk，GB2312，GB18030

字符必须编码后才能被计算机处理。计算机使用的缺省编码方式就是计算机的内码。早期的计算机使用7位的ASCII编码，为了处理汉字，程序员设 计了用于简体中文的GB2312和用于繁体中文的big5。

GB2312(1980年)一共收录了7445个字符，包括6763个汉字和682 个其它符号。汉字区的内码范围高字节从B0-F7，低字节从A1-FE，占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。

GB2312 支持的汉字太少。1995年的汉字扩展规范GBK1.0收录了21886个符号，它分为汉字区和图形符号区。汉字区包括21003个字符。2000年的 GB18030是取代GBK1.0的正式国家标准。该标准收录了27484个汉字，同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字。现在的PC平 台必须支持GB18030，对嵌入式产品暂不作要求。所以手机、MP3一般只支持GB2312。

从ASCII、GB2312、GBK到 GB18030，这些编码方法是向下兼容的，即同一个字符在这些方案中总是有相同的编码，后面的标准支持更多的字符。在这些编码中，英文和中文可以统一地 处理。区分中文编码的方法是高字节的最高位不为0。按照程序员的称呼，GB2312、GBK到GB18030都属于双字节字符集 (DBCS)。

GB 18030是中国所有非手持/嵌入式计算机系统的强制实施标准.

2.UTF－8，UTF－16，UTF-32

UTF-8, 8bit编码, ASCII不作变换, 其他字符做变长编码, 每个字符1-3 byte. 通常作为外码. 有以下优点:

* 与CPU字节顺序无关, 可以在不同平台之间交流

* 容错能力高, 任何一个字节损坏后, 最多只会导致一个编码码位损失, 不会链锁错误(如GB码错一个字节就会整行乱码)

UTF-16, 16bit编码, 是变长码, 大致相当于20位编码, 值在0到0x10FFFF之间, 基本上就是unicode编码的实现. 它是变长码, 与CPU字序有关, 但因为最省空间, 常作为网络传输的外码.

UTF- 16是unicode的preferred encoding.

UTF-32, 仅使用了unicode范围(0到0x10FFFF)的32位编码, 相当于UCS-4的子集.

14、给我一个你最常见到的runtime exception

答：常见的运行时异常有如下 这些ArithmeticException, ArrayStoreException, BufferOverflowException, BufferUnderflowException, CannotRedoException, CannotUndoException, ClassCastException, CMMException, ConcurrentModificationException, DOMException, EmptyStackException, IllegalArgumentException, IllegalMonitorStateException, IllegalPathStateException, IllegalStateException, ImagingOpException, IndexOutOfBoundsException, MissingResourceException, NegativeArraySizeException, NoSuchElementException, NullPointerException, ProfileDataException, ProviderException, RasterFormatException, SecurityException, SystemException, UndeclaredThrowableException, UnmodifiableSetException, UnsupportedOperationException

5、Collection和Collections的区

别

答：Collection是集合类的上级接口，继承与他的接口主要有Set 和List.

Collections是针对集合类的一个帮助 类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作

15、error和exception有什么区别

答：error 表示恢复不是不可能但很困难的情况下的一种严重问题。比如说内存溢出。不可能指望程序能处理这样的情况

exception 表示一种设计或实现问题。 也就是说，它表示如果程序运行正常，从不会发生的情况

16、List, Set, Map是否继承自Collection接口

答： List，Set是，Map不是

17、abstract class和interface有什么区别

答：声明方法的存在而不去实现 它的类被叫做抽象类（abstract class），它用于要创建一个体现 某些基本行为的类，并为该类声明方法，但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例。不能有抽象构造函 数或抽象静态方法。Abstract 类的子类为它们父类中的所 有抽象方法提供实现，否则它们也是抽象类为。取而代之，在子类中实现该方法。知道其行为的其它类可以在类中实现这些方法

接口（interface）是抽象类的变体。在接 口中，所有方法都是抽象的。多继承性可通过实现这样的接口而获得。接口中的所有方法都是抽象的，没有一个有程序体。接口只可以定义static final成员变量。接口的实现与子类相似，除了该实现类不能从接口定义中继承行为。当 类实现特殊接口时，它定义（即将程序体给予）所有这种接口的方法。然后，它可以在实现了该接口的类的任何对象上调用接口的方法。由于有抽象类，它允许使用 接口名作为引用变量的类型。通常的动态联编将生效。引用可以转换到接口类型或从接口类型转换，instanceof 运算符可以用来决定某对象的类是否实现了接口

6、Java基本概念：集合类 List/Set/Map... 的区别和联系

Collection：List、Set

Map：HashMap、 HashTable

如何在它们之间选择

一、 Array ， Arrays

Java所有“存储及随机访问一连串对象”的做 法，array是最有效率的一种。

1、

效率高，但容量固定且无法动态改变。

array 还有一个缺点是，无法判断其中实际存有多少元素，length只是告诉我们array的容量。

2、 Java中有一个Arrays类，专门用来操作array。

arrays中拥有一组static函数，

equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相 等。

fill()：将值填入array中。

sort()：用来对array进行排序。

binarySearch()：在排好序的 array中寻找元素。

System.arraycopy()：array的复制。

二、 Collection ， Map

若撰

写程序时不知道究竟需要多少对象，需要在空间不足 时自动扩增容量，则需要使用容器类库，array不适用。

1、 Collection 和 Map 的区别

容器内每个为之所存储的元素个 数不同。

Collection类型者，每个位置只有一个元素。

Map类型者，持有 key-value pair，像个小型数据库。

2、各自旗下的子类关系

Collection

--List： 将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。

--ArrayList / LinkedList / Vector

--Set ： 不能含有重复的元素

--HashSet / TreeSet

Map

--HashMap

--HashTable

--TreeMap

Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│ 　└Stack

└Set

Map

├Hashtable

├HashMap

└WeakHashMap

Collection 接口

　　Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素 （Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

　 　所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。

　　如何遍历Collection中的每一个元素？不论Collection的实际类型如 何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：

　 　　　Iterator it = collection.iterator(); // 获得一个迭代子

　　　　 while(it.hasNext()) {

　　　　　　Object obj = it.next(); // 得到下一个元素

　　　 　}

　　由Collection接口派生的两个接口是List和Set。

List接口

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

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

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

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

LinkedList 类

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

或双向队列（deque）。

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

　　　　List list = Collections.synchronizedList(new LinkedList(...));

ArrayList类

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

size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n 个元素需要O(n)的时间。其他的方法运行时间为线性。

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

　　和LinkedList一样，ArrayList也是非同步的 （unsynchronized）。

Vector类

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

Stack 类

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

Set 接口

　　Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set 最多有一个null元素。

　　很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。

　　请注 意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Map 接口

　　请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key 只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Hashtable 类

　　Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者 value。

　　添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。

Hashtable 通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡

。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。

使 用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：

　　 　　Hashtable numbers = new Hashtable();

　　　　numbers.put(“one”, new Integer(1));

　　　　numbers.put(“two”, new Integer(2));

　　　　 numbers.put(“three”, new Integer(3));

　　要取出一个数，比如2，用相应的key：

　　　　 Integer n = (Integer)numbers.get(“two”);

　　　　System.out.println(“two = ” + n);

　　由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现 hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照 散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的 hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的 hashCode()方法，能加快哈希表的操作。

　　如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的 get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。

　　 Hashtable是同步的。

HashMap类

　　HashMap和Hashtable类似，不同之处在于HashMap是非同 步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

WeakHashMap 类

　　WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC 回收。

总结

　　如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList， 如果需要快速随机访问元素，应该使用ArrayList。

　　如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较 高，如果多个线程可能同时操作一个类，应该使用同步的类。

　　要特别注意对哈希表的操作，作为key的对象要正确复写equals和 hashCode方法。

　　尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成 LinkedList时，客户端代码不用改变。这就是针对抽象编程。

3、其他特征

* List，Set，Map将持有对象一律视为Object型别。

* Collection、List、Set、Map都是接口，不能实例化。

继承自它们的 ArrayList, Vector, HashTable, HashMap是具象class，这些才可被实例化。

* vector容器确切知道它所持有的对象隶属什么型别。vector不进行边界检查。

三、 Collections

Collections 是针对集合类的一个帮助类。提供了一系列静态方法实现对各 种集合的搜索、排序、线程完全化等操作。

相当于对Array进行类似操作的类——Arrays。

如，Collections.max(Collection coll); 取coll中最大的元素。

Collections.sort(List list); 对list中元素排序

四、 如何选择？

1、容器类和Array的区别、择取

* 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息copy一份至数列某位置。

* 一旦将对象置入容器内，便损失了该对象的型别信息。

2、

* 在各种Lists中，最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList()；

Vector总是比ArrayList慢，所以要尽量避免使用。

* 在各种Sets中，HashSet通常优于HashTree（插入、查找）。只有当需要产生一个经过排序的序列，才用TreeSet。

HashTree存在的唯一理由：能够维护其内元素的排序状态。

* 在各种Maps中

HashMap用于快速查找。

* 当元素个数固定，用Array，因为Array效率是最高的。

结论：最常用的是ArrayList，HashSet，HashMap，Array。

注意：

1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。

2、Set和Collection拥有一模一样的接口。

3、List，可以通过get()方法来一次取出一个元素。 使用数字来选择一堆对象中的一个，get(0)...。(add/get)

4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。

5、Map用 put(k,v) / get(k)，还可以使用 containsKey()/containsValue()来检查其中是否含有某个key/value。

HashMap会利用对象的hashCode来快速找到key。

* hashing

哈希码就是将对象的信息经过一些转变形成一个独一无二的int值，这个值存储在一个array中。

我们都知道所有存储结构中，array查找速度是最快的。所以，可以加速查找。

发生碰撞时，让array指向多个values。即，数组每个位置上又生成一个梿表。

6、Map中元素，可以将key序列、value序列单独抽取出来。

使用keySet()抽取key序列，将map中的所有keys生成一个Set。

使用values()抽取value序列，将 map中的所有values生成一个Collection。

为什么一个生成Set，一个生成Collection？那是因为，key总是独 一无二的，value允许重复。

Collection List Set Map 区别记忆

这些都代表了Java中的集合，这 里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还

存在同步方面的差异，见上一篇相关文章。

有序否 允许元素重复否

Collection 否 是

List 是 是

Set AbstractSet 否 否

HashSet

TreeSet 是（用二叉树排序）

Map AbstractMap 否 使 用key-value来映射和存储数据，Key必 须惟一，value可以重复

HashMap

TreeMap 是（用二叉树排序）

http://tb.blog.csdn.net/TrackBack.aspx?PostId=584112

List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和 LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。 ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在 链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator 则继承了Iterator的思想，并提供了对List进行双向遍历的方法。

Set接口也是Collection的一种扩展，而与List不 同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元 素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存 放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就 应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。 集合框架中还有两个很实用的公用类：Collections和Arrays。Collections提供了对一个Collection容器进行诸如排序、 复制、查找和填充等一些非常有用的方法，Arrays则是对一个数组进行类似的操作。

Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允 许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象， 结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象 与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得 到的到底是那一个

键所对应的值对象）。Map有两种比较常用的实现：HashMap和 TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如 firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。 键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

7、Java语言中链表和双向链表

链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。

　　class Node

　　{

　　Object data;

　　Node next;//指向下一个结点

　　}

　　将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的示意图：

　　链表的数据结构

　　我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。

　　链表类List的源代码如下：

　　import java.io.*;

　　public class List

　　{

　　/*用变量来实现表头*/

　　private Node Head=null;

　　private Node Tai

l=null;

　　private Node Pointer=null;

　　private int Length=0;

　　public void deleteAll()

　　/*清空整个链表*/

　　{

　　Head=null;

　　Tail=null;

　　Pointer=null;

　　Length=0;

　　}

　　public void reset()

　　/*链表复位，使第一个结点成为当前结点*/

　　{

　　Pointer=null;

　　}

　　public boolean isEmpty()

　　/*判断链表是否为空*/

　　{

　　return(Length==0);

　　}

　　public boolean isEnd()

　　/*判断当前结点是否为最后一个结点*/

　　{

　　if(Length==0)

　　　throw new java.lang.NullPointerException();

　　else if(Length==1)

　　　return true;

　　else

　　　return(cursor()==Tail);

　　}

　　public Object nextNode()

　　/*返回当前结点的下一个结点的值，并使其成为当前结点*/

　　{

　　if(Length==1)

　　　throw new java.util.NoSuchElementException();

　　else if(Length==0)

　　　throw new java.lang.NullPointerException();

　　else

　　{

　　　Node temp=cursor();

　　　Pointer=temp;

　　　if(temp!=Tail)

　　　　return(temp.next.data);

　　　else

　　　　throw new java.util.NoSuchElementException();

　　}

　　}

　　public Object currentNode()

　　/*返回当前结点的值*/

　　{

　　Node temp=cursor();

　　return temp.data;

　　}

　　

　　public void insert(Object d)

　　/*在当前结点前插入一个结点，并使其成为当前结点*/

　　{

　　Node e=new Node(d);

　　if(Length==0)

　　{

　　　Tail=e;

　　　Head=e;

　　}

　　else

　　{

　　　Node temp=cursor();

　　　e.next=temp;

　　　if(Pointer==null)

　　　　Head=e;

　　　else

　　　　Pointer.next=e;

　　}

　　Length＋＋;

　　}

　　public int size()

　　/*返回链表的大小*/

　　{

　　return (Length);

　　}

　　public Object remove()

　　/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/

　　{

　　Object temp;

　　if(Length==0)

　　　throw new java.util.NoSuchElementException();

　　else if(Length==1)

　　{

　　　temp=Head.data;

　　　deleteAll();

　　}

　　else

　　{

　　　Node cur=cursor();

　　　temp=cur.data;

　　　if(cur==Head)

　　　　Head=cur.next;

　　　else if(cur==Tail)

　　　{

　　　　Pointer.next=null;

　　　　Tail=Pointer;

　　　　reset();

　　　}

　　　else

　　　　Pointer.next=cur.next;

　　　　Length－－;

　　}

　　return temp;

　　}

　　private Node cursor()

　　/*返回当前结点的指针*/

　　{

　　if(Head==null)

　　　throw new java.lang.NullPointerException();

　　else if(Pointer==null)

　　　return Head;

　　else

　　　return Pointer.next;

　　}

　　public static void main(String[] args)

　　/*链表的简单应用举例*/

　　{

　　List a=new List ();

　　for(int i=1;i

　　　a.insert(new Integer(i));

　　　System.out.println(a.currentNode());

　　　while(!a.isEnd())

　　　　System.out.println(a.nextNode());

　　　　a.reset();

　　　　while(!a.isEnd())

　　　　{

　　　　　a.remove();

　　　　}

　　　　a.remove();

　　　　a.reset();

　　　　if(a.isEmpty())

　　　　　System.out.println("There is no Node in List \n");

　　　　　System.in.println("You can press return to quit\n");

　　　　try

　　　　{

　　　　　System.in.read();

　　　　　//确保用户看清程序运行结果

　　　　}

　　　　catch(IOException e)

　　　　{}

　　　}

　　}

　　class Node

　　/*构成链表的结点定义*/

　　{

　　　Object data;

　　　Node next;

　　　Node(Object d)

　　　{

　　　　data=d;

　　　　next=null;

　　　}

　　}

　　读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。

　　可以用这样的代码来实现：

　　class Node

　　{

　　Object data;

　　Node next;

　　Node previous;

　　Node(Object d)

　　{

　　data=d;

　　next=null;

　　previous=null;

　　}

　　}

　　当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。

(1)简单链表

Java代码

1 package ChapterFive;

2

3 class Link {

4

5 public E data;

6

7 public Link next;

8

9 public Link(E data) {

10 this.data = data;

11 }

12 }

13

14 class LinkList {

15

16 public Link first;

17 //链表中数据项的个数

18 public int size;

19

20 public LinkList() {

21 first = null;

22 size = 0;

23 }

24 //在表头插入新的数据

25 public void insertFirst(E value) {

26 Link link = new Link(value);

27 link.next = first;

28 first = link;

29 size++;

30 }

31 //判断链表是否为空

32 public boolean isEmpty() {

33 return size == 0;

34 }

35 //删除表头

36 public Link deleteFirst() {

37 Link temp = first;

38 first = first.next;

39 size--;

40 return temp;

41 }

42 //输出链表中的所有数据

43 public void display() {

44 Link curr = first;

45 while (curr != null) {

46 System.out.print(curr.data + " ");

47 curr = curr.next;

48 }

49 System.out.println();

50 }

51 //返回链表中数据项的个数

52 public int size() {

53 return size;

54 }

55 //获取从头至尾的第i个数据项

56 public Link get(int i) {

57 if (i > size() - 1 || i

58 try {

59 throw new IndexOutOfBoundsException();

60 } catch (Exception e) {

61 e.printStackTrace();

62 }

63 Link curr = first;

64 for (int n = 0; n

65 if (n == i)

66 return curr;

67 else

68 curr = curr.next;

69 }

70 return null;

71 }

72 //输出从头至尾的第i个数据项

73 public void remove(int i) {

74 if (i == 0)

75 deleteFirst();

76 else if (i == size() - 1)

77 get(i - 1).next = null;

78 else {

79 get(i - 1).next = get(i + 1);

80 }

81 size--;

82 }

83 }

84

85 public class Link_list {

86 public static void main(String[] args) {

87 LinkList ll = new LinkList();

88 for (int i = 0; i

89 Long value = (long) (Math.random() * 100);

90 ll.insertFirst(value);

91 }

92 ll.display();

93 while (!ll.isEmpty()) {

94 ll.deleteFirst();

95 ll.display();

96 }

97 System.out.println("Ok");

98 }

99 }

(2)链栈

Java代码

100 package ChapterFive;

101

102 class LinkStack {

103

104 LinkList linkList;

105

106 int size;

107

108 public LinkStack() {

109 size = 0;

110 linkList = new LinkList();

111 }

112 //入栈

113 public void push(E value) {

114 linkList.insertFirst(value);

115 size++;

116 }

117 //出栈

118 public Link pop() {

119 size--;

120 return linkList.deleteFirst();

121 }

122 //返回栈顶元素

123 public Link top() {

124 return linkList.first;

125 }

126 //判断栈是否为空

127 public boolean isEmpty() {

128 return size == 0;

129 }

130 //显示栈中的全部数据

131 public void display() {

132 linkList.display();

133 }

134 }

135

136 public class Link_stack {

137 public static void main(String[] args) {

138 LinkStack ls = new LinkStack();

139 for (int i = 0; i

140 Long value = new Long((long) (Math.random() * 100));

141 ls.push(value);

142 }

143 while (!ls.isEmpty()) {

144

ls.pop();

145 ls.display();

146 }

147 System.out.println("Ok");

148 }

149 }

(3)有序表

Java代码

150 package ChapterFive;

151

152 class SortedLink {

153

154 public Link first;

155

156 int size;

157

158 public SortedLink() {

159 first = null;

160 size = 0;

161 }

162 //向有序链表中插入数据

163 public void insert(long value) {

164 Link newLink = new Link(value);

165 Link previous = null;

166 Link curr = first;

167 while (curr != null && (value > curr.data)) {

168 previous = curr;

169 curr = curr.next;

170 }

171 if (previous == null)// 链表为空(在表头插入)

172 first = newLink;

173 else

174 previous.next = newLink;//插入新的节点

175 newLink.next = curr;

176 size++;

177 }

178 //删除第一个节点

179 public Link remove() {

180 Link temp = first;

181 first = first.next;

182 size--;

183 return temp;

184 }

185 //判断链表是否为空

186 public boolean isEmpty() {

187 return size == 0;

188 }

189 //输出链表的所有数据

190 public void display() {

191 Link curr = first;

192 while (curr != null) {

193 System.out.print(curr.data + " ");

194 curr = curr.next;

195 }

196 System.out.println();

197 }

198 }

199

200 public class SortedLinkApp {

201 public static void main(String[] args) {

202 SortedLink sl = new SortedLink();

203 for (int i = 0; i

204 sl.insert((long) (Math.random() * 100));

205 }

206 while (!sl.isEmpty()) {

207 sl.remove();

208 sl.display();

209 }

210 }

211 }

(4)双向链表

Java代码

212 package ChapterFive;

213

214 class DoubleLink {

215

216 public Link first;

217

218 public Link last;

219

220 int size;

221

222 @SuppressWarnings("hiding")

223 class Link {

224 public E data;

225

226 public Link next;// 链表的下一项

227

228 public Link previous;// 链表的前一项

229

230 public Link(E value) {

231 this.data = value;

232 }

233 }

234

235 public DoubleLink() {

236 first = null;

237 last = null;

238 size = 0;

239 }

240

241 // 在链表的首部插入一项

242 public void insertFirst(E value) {

243

Link newLink = new Link(value);

244 if (isEmpty())// 如果链表为空则first == last

245 last = newLink;

246 else

247 first.previous = newLink;// 确定原first与newLink的前后关系

248 newLink.next = first;

249 first = newLink;// 设置新的first值

250 size++;

251 }

252

253 // 在链表的尾部插入一项

254 public void insertLast(E value) {

255 Link newLink = new Link(value);

256 if (isEmpty())// 如果链表为空则last == first

257 first = newLink;

258 else {

259 last.next = newLink;// 确定原last与newLink的前后关系

260 newLink.previous = last;

261 }

262 last = newLink;// 设置新的last值

263 size++;

264 }

265

266 // 删除双向链表的表头

267 public Link deleteFirst() {

268 Link temp = first;

269 if (first.next == null)// 链表中只有一项数据

270 last = null;

271 else

272 first.next.previous = null;// 销毁原链表的头部

273 first = first.next;

274 size--;

275 return temp;

276 }

277

278 // 删除链表的最后一项

279 public Link deleteLast() {

280 Link temp = last;

281 if (first.next == null)// 链表中只有一项数据

282 first = null;

283 else

284 last.previous.next = null;// 销毁原链表的尾部

285 last = last.previous;

286 size--;

287 return temp;

288 }

289

290 // 判断链表是否为空

291 public boolean isEmpty() {

292 return size == 0;

293 }

294

295 // 输出链表中的所有数据项

296 public void display() {

297 Link curr = first;

298 while (curr != null) {

299 System.out.print(curr.data + " ");

300 curr = curr.next;

301 }

302 System.out.println();

303 }

304 }

305

306 public class DoubleLinkApp {

307 public static void main(String[] args) {

308 DoubleLink dl = new DoubleLink();

309 for (int i = 0; i

310 dl.insertFirst((int) (Math.random() * 100));

311 }

312 for (int i = 0; i

313 dl.insertLast((int) (Math.random() * 100));

314 }

315 dl.display();

316 while (!dl.isEmpty()) {

317 dl.deleteFirst();

318 dl.deleteLast();

319 dl.display();

320 }

321 System.out.println("Ok");

322 }

323 }