Java 基础实习 - List

在看 JDK 1.6 的源码，用以补习自己的 Java 基础。

java.util 包中包含 collection 框架、遗留的 collection 类、事件模型、日期和时间设施、国际化和各种实用工具类（字符串标记生成器、随机数生成器和位数组）。

在这里对 List 进行一个小结。
在接口定义中描述为：

引用

有序的 collection （也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。与 set 不同，列表通常允许重复的元素。……

简单的说 List 的特性：有序，允许重复元素，实现迭代器。

下面看具体的实现类，包括
Vector
Stack
ArrayList
LinkedList
ArrayDeque

Vector 和 Stack 是遗留的 collection 类。Vector 的所有方法都标识有 synchronized 以保证其线程同步的特性。

Stack 继承至 Vector 并添加了堆栈相关的特性（pop, push, peek）。因为其继承关系，其所有方法也是线程安全的。

ArrayList 是在 JDK 1.2 中对数据结构相关的工具类重新抽象整理的结果，在功能上与 Vector 完全一至，但去除了对线程安全的保证。
不过可以通过

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

来实现线程安全。故在代码中应该优先考虑使用 ArrayList 而非 Vector。

ArrayList 使用数组的形式实现数据存储，在添加数据的过程中会按照 (size * 3 )/2 + 1 的规则自动扩充。对比 Vector，Vector 可设置一个自增量，在需要扩充时自动增加自增量大小的空间或自动增大到原大小的一倍（自增量设置为0或小于0时）。

LinkedList 使用内部类的形式存储数据，失去了 ArrayList 随机访问数据的特性（可随机访问的列表会实现标识接口 RandomAccess）。LinkedList 实现了 Queue 和 Deque 接口，使其实现了队列及双向队列的特性。但在 JDK 1.6 版本之后，建议优先使用 ArrayDeque 来实现队列和堆栈，以获得更高的运行时效率。
在数据量非常大的时候，可以使用 LinkedList 以获得平衡的数据添加效率。因为 LinkedList 不需要去重新开辟新的 array 空间。(add at 2011-03-31)

以上列表的实现都可以插入 null，但这一操作是不被推荐的。因为在一些方法中，null 会用作特殊用途。如队列（Queue），pop()方法返回 null 表示队列为空。

ArrayDeque 是在 JDK 1.6 中引入的新类。此类实现了 List, Deque 接口，是一个双向队列实现。在此队列中使用数组存储数据，使用两个指针记录列队的头尾以实现循环队列。因为是循环队列的实现，因此该队列牺牲了随机访问的特性而节约了空间的开销。但其访问效率在 LinkedList 之上，在 JDK 文档中被推荐代替 LinkedList 和 Stack 类。

========
一些好玩的测试：

public void testHashCode() {
	List list = new ArrayList();
	System.out.println("hashcode:" + list.hashCode()); //  hashcode:1
	list.add(null);
	System.out.println("hashcode:" + list.hashCode()); // hashcode:31
	list.add(null);
	System.out.println("hashcode:" + list.hashCode()); // hashcode:961
}

public void testTime() {
	int N = 100000;

	List<String> arrayList = new ArrayList<String>(N);
	List<String> linkedList = new LinkedList<String>();

	for (int i = 0; i < N; i++) {
		arrayList.add("" + i);
		linkedList.add("" + i);
	}

	{
		Iterator<String> it = arrayList.iterator();
		Date start = new Date();
		StringBuffer sb = new StringBuffer();
		while (it.hasNext()) {
			sb.append(it.next());
		}
		Date end = new Date();
		System.out.println("\ntime for arrayList used iterator:"
				+ (end.getTime() - start.getTime()));

		start = new Date();
		sb = new StringBuffer();
		for (int i = 0; i < arrayList.size(); i++) {
			sb.append(arrayList.get(i));
		}
		end = new Date();
		System.out.println("\ntime for arrayList used for loop:"
				+ (end.getTime() - start.getTime()));
	}
	{
		Iterator<String> it = linkedList.iterator();
		Date start = new Date();
		StringBuffer sb = new StringBuffer();
		while (it.hasNext()) {
			sb.append(it.next());
		}
		Date end = new Date();
		System.out.println("\ntime for linkedList used iterator:"
				+ (end.getTime() - start.getTime()));

		start = new Date();
		sb = new StringBuffer();
		for (int i = 0; i < linkedList.size(); i++) {
			sb.append(linkedList.get(i));
		}
		end = new Date();
		System.out.println("\ntime for linkedList used for loop:"
				+ (end.getTime() - start.getTime()));
	}
}
// output:(单位是毫秒)
// time for arrayList used iterator:16
// time for arrayList used for loop:15
// time for linkedList used iterator:0
// time for linkedList used for loop:92168

public void testArrayCopy () {
	// Prepare arrays
	User[] array = new User[10];
	for (int i = 0; i < 10; i++) {
		array[i] = new User("" + i);
	}
	
	User[] newArray = new User[10];
	System.arraycopy(array, 2, newArray, 1, 8);
	for (User user:newArray) {
		System.out.print(", " + user);
	}
	System.out.println();
	// modify array
	newArray[1].setName("change");
	for (int i = 0; i < 10; i++) {
		System.out.print(", " + array[i]);
	}
}
class User{
	String name;
	protected User() {
	}
	public User(String name) {
		this.name = name;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String toString() {
		return " \"" + name + "\" ";
	}
}
// output:
// , null,  "2" ,  "3" ,  "4" ,  "5" ,  "6" ,  "7" ,  "8" ,  "9" , null
// ,  "0" ,  "1" ,  "change" ,  "3" ,  "4" ,  "5" ,  "6" ,  "7" ,  "8" ,  "9"

public void testToArray() {
	List<String> list = new ArrayList<String>();
	list.add("1");
	list.add("2");
	list.add("3");
	
	String[] str = new String[5];
	str[3] = "4";
	str[4] = "5";
	String[] newStr = list.toArray(str);
	for (String s : newStr) {
		System.out.print(", " + s);
	}
}
// output: , 1, 2, 3, null, 5