程序员面试必考题（十六）--Java中的数组链表

1. ArrayList类

ArrayList类是Java标准包java.util中的一部分。ArrayList提供了保存一组对象的另一种方法，与数组相比，它有3大好处，如下所示

(1) 程序中 ArrayList 的大小变化是按需进行的，而数组在创建时设置了固定的长度。

(2)  在ArrayList中，最后一个位置总是list.size()-1，而在一个部分填满的数组中，程序员必须自己记录当前使用的最后位置。

(3) 对于ArrayList，可以只用一个语句进行插入或删除操作。元素的任何移动自动处理。但在数组中，插入或删除需要写代码来移动元素。

2. 泛型

在Java 5.0中，ArrayList类是泛型，就是说它带一个类型参数。下面是ArrayList类头的一部分：

public class ArrayList<E> ...

类型参数E是占位符，可以是任何非内置类型，在程序中使用ArrayList时必须定义类型。这样做的目的，表示要让ArrayList被限定为一个具体的数据类型。编译时要检查类型，并且编译程序记录下元素的类型，当访问ArrayList中对象时不需要转型。所有的这些措施都为程序提供了基本的类型安全。注意，在Java中数组没有泛型特性。

3. ArrayList的方法

ArrayList类中的常用方法列在表1中。

表 1 ArrayList 类的主要方法

表1中的每个方法（add、get、remove、set）都有一个index参数，如果index越界，将抛出IndexOutOfBoundsException。对于get、remove和set，如果index< 0 || index >= size()则index越界。

但对于方法add，在表尾添加元素是可行的。所以，如果index< 0 || index > size()，index是越界的。

【例题1】 Consider writing aprogram that reads the lines of any text file into a sequential list of lines. Whichof the following is a good reason to implement the list with an ArrayList of String objects rather than anarray of String objects?

A．The get and set methods of ArrayList are more convenient than the []notation for arrays.

B．The size method of ArrayList provides instant access to the length ofthe list.

C．An ArrayList can contain objects of any type, which leads to greatergenerality.

D．If any particular text file is unexpectedly long, the ArrayList willautomatically be resized. The array, by contrast, may go out of bounds.

E．The String methods are easier to use with an ArrayList than with anarray.

解：D。数组是定长的，如果改变数据集大小的话，数组不能缩涨。而ArrayList自动改变表的大小。选项A是错误的：[]符号是简洁的，易于使用。选项B不是合理的理由，因为数组arr通过arr.length也能在常数阶时间内访问长度。选项C是非法的，因为数组也可以包含对象。而且，它对所给程序的概括离题了：表必须保存String对象。选项E是错误的：不管String对象是arr[i]还是list.get(i)，String方法都同样方便调用。

【例题2】 Which declaration willcause an error?

I．ArrayList<String>stringList = new ArrayList<String>();

II．ArrayList<int>intList = new ArrayList<int>();

III．ArrayList<Comparable> compList = newArrayList<Comparable>();

A．I only        B．II only       C．III only        D．I and III only      E．II and III only

解：B。泛型ArrayList的类型参数必须是类类型，不能是内置数据类型。

4. 自动装箱和自动拆箱

我们已经知道，ArrayList包含的必须是对象，而不能是像double和int这样的内置数据类型。所以如果要将数值插入到ArrayList中时，必须要先将这个数装箱——放到象Integer和Double这样的包装类中。

自动装箱是指内置类型自动包装在它们的包装类中。

为了得到保存在ArrayList中Integer（或是Double）中的数值，要调用intValue()（或是doubleValue()）方法。

自动拆箱是将包装类自动转换为对应的内置数据类型。如果程序要自动拆箱的对象是null，则方法将抛出NullPointerException。

自动装箱和自动拆箱可以减少代码混乱，这些操作都是系统自动执行的，这使得系统效率降低。赋值及访问数组中内置类型的数据比ArrayList的效率要高许多。所以程序中应该先考虑使用数组来操作数值序列，而不需要使用对象。

【 例3 】 Consider thesedeclarations:

ArrayList<String>stringList = new ArrayList<String>();

Stringch = " ";

IntegerintOb = new Integer(5);

Whichstatement will cause an error?

A．stringList.add(ch);

B．stringList.add(new String("handy andy"));

C．stringList.add(intOb.toString());

D．stringList.add(ch + 8);

E．stringList.add(intOb + 8);

解：E。添加到strList中的所有元素必须是String类型的。除选项E外的每个选项都满足。注意，在选项D中，因为ch是String，表达式ch + 8得到一个String（仅仅因为一个操作数必须是String，所以整个表达式都要转为String）。选项E中，intOb和8都不是String。

5.使用ArrayList

例4 使用ArrayList示例。

//Create an ArrayList containing 0 1 4 9.

ArrayList<Integer> list = newArrayList<Integer>();

for (int i = 0; i < 4; i++)

list.add(i* i);    //exampleof auto-boxing

//i*i wrapped in an Integer before insertion

Integer intOb = list.get(2);    //assignsInteger with value 4 to intOb.

//Leaves list unchanged.

int n = list.get(3);  //example of auto-unboxing

//Integeris retrieved and converted to int

//ncontains 9

Integer x = list.set(3, 5);   //listis 0 1 4 5

//xcontains Integer with value 9

x = list.remove(2); //list is 0 1 5

//xcontains Integer with value 4

list.add(1, 7); //list is 0 7 1 5

list.add(2, 8); //list is 0 7 8 1 5

例6.14 使用ArrayList示例。

//Traversing an ArrayList of Integer.

//Print the elements of list, one per line.

for (Integer i : list)

System.out.println(i);

例7 使用ArrayList示例。

/* Precondition: ArrayList list containsInteger values

* sorted in increasing order.

* Postcondition: value inserted in its correctposition in list. */

public static voidinsert(ArrayList<Integer> list, Integer value)

{

intindex = 0;

//findinsertion point

while(index < list.size() && value.compareTo(list.get(index)) > 0)

index++;

//insertvalue

list.add(index,value);

}

假定value大于list中的所有元素。如果忽略了测试的第1部分，即index< list.size()，则insert方法将抛出IndexOutOfBoundsException。