Collection之链表

在Java语言中，所有的链表都是双向链接的（doubly linked），每个节点存放着序列中下一个节点的引用以及指向前驱节点的引用（可以通过调用AbstractCollection类中的toString方法打印出链表中所有元素）

package com.chensl.collection;
import java.util.*;
public class LinkedListTest {
	/**
	 * 本程序演示链表操作
	 * @author chensl
	 * @since 2010-9-2
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> linkedList=new LinkedList<String>();//其中LinkedList 实现了List
		linkedList.add("张三");
		linkedList.add("李四");
		linkedList.add("王五");	
		Iterator<String> iter = linkedList.iterator();
		String first = iter.next(); //访问第一个元素
		String second = iter.next(); //访问第二个元素
		iter.remove();  //删除最后访问的元素
	}
}

 

 

在Iterator接口中没有add方法，集合类库提供了子接口ListIterator中包含add方法：

interface ListIterator<E> extends Iterator<E>
{
    void add(E element);         //与Collection.add不同，不返回boolean类型的值，而是假定添加操作总会改变链表
    ......
}

 

ListIterator接口有两个方法可以用来反向遍历链表,即：

E  previous()  

boolean   hasPrevious()

其中，previous()与next()方法一样， 返回被越过的对象。

LinkedList类的listIterator方法返回一个实现了ListIterator接口的迭代器对象，

ListIterator<String> iter = linkedList.listItertor();

 add方法在迭代器位置之前添加一个新对象，下面的代码将越过链表中的第一个元素，并在第二个元素之前添加“赵六”

    List<String> linkedList=new LinkedList<String>();//其中LinkedList 实现了List
    linkedList.add("张三");
    linkedList.add("李四");
    linkedList.add("王五");
    ListIterator<String> iter = linkedList.listIterator();
    iter.next();
    iter.add("赵六");

另外， set方法用一个新元素取代调用next和previous方法返回的上一个元素，例如，下面的代码将用一个新值取代链表的第一个元素：

ListIterator<String> iter3 = linkedList.listIterator();
	String oldValue = iter3.next();  //返回第一个元素
	iter3.set("新值");

 如果迭代器发现它的集合被另一个迭代器修改了，或者该集合被自身的方法修改了，就会抛出一个ConcurrentModificationException异常。

 

完整示例程序如下：

package com.chensl.collection;
import java.util.*;
public class LinkedListTest {
	/**
	 * 本程序演示链表操作
	 * @author chensl
	 * @since 2010-9-2
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> linkedList=new LinkedList<String>();//其中LinkedList 实现了List
		linkedList.add("张三");
		linkedList.add("李四");
		linkedList.add("王五");
		System.out.println("第1次: "+linkedList);
		ListIterator<String> iter = linkedList.listIterator();
		iter.next();
		iter.add("赵六");
		System.out.println("第2次: "+linkedList);
		Iterator<String> iter2 = linkedList.iterator();
		String first = iter2.next(); //访问第一个元素
		String second = iter2.next(); //访问第二个元素
		iter2.remove();  //删除最后访问的元素
		
		System.out.println("第3次: "+linkedList);
		ListIterator<String> iter3 = linkedList.listIterator();
		String oldValue = iter3.next();  //返回第一个元素
		iter3.set("新值");
		
		System.out.println("第4次: "+linkedList);
	}
}

 

结果输出如下：

 

第1次: [张三, 李四, 王五]
第2次: [张三, 赵六, 李四, 王五]
第3次: [张三, 李四, 王五]
第4次: [新值, 李四, 王五]