《Java数据结构和算法》学习笔记(4)——链表

每篇笔记都会附上随书的Applet演示程序，有算法看不明白的，可以下载Applet运行起来（直接打开html文件即可），可以很容易地看清楚算法的每一步。

链表

链表简单的说就是个对象链，一个对象里包含另一个对象的引用。链表类的成员只有一个：这个链表的第一个链接点。只要通过第一个链接点，就能得到链表里所有的其它链接点。下面是一个链表的实现：

package dsaa.array;
/**
 * @(#)LinkList.java 2008-12-27 下午07:02:17
 * 
 * @author Qiu Maoyuan
 * Link List
 */
public class LinkList<E> {

	private Link first;
	
	public void addFirst(E value){
		Link newElement = new Link(value);
		newElement.next = first;
		first = newElement;
	}
	
	public E getFirst(){
		if(isEmpty())
			throw new IllegalStateException("Linklist is empty");
		return first.element;
	}
	
	public boolean isEmpty(){
		return first == null;
	}
	
	public E removeFirst(){
		if(isEmpty())
			throw new IllegalStateException("Linklist is empty");
		E value = first.element;
		first = first.next;
		return value;
	}
	
	public boolean delete(E element){
		if(isEmpty())
			return false;
		Link current = first;
		Link previous = first;
		while(!element.equals(current.element)){
			if(current.next == null){
				return false;
			} else {
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return true;
	}

	@Override
	public String toString(){
		StringBuilder buffer = new StringBuilder();
		Link current = first;
		while(current != null){
			buffer.append(current.toString());
			current = current.next;
		}
		return buffer.toString();
	}
	
	private class Link{
		
		private E element;
		
		private Link next;
		
		public Link(E element){
			this.element = element;
		}

		@Override
		public String toString(){
			return "[" + element.toString() + "]";
		}
	}
}

双端链表与普通链表的区别就是：双端链表多了一个对链表尾部元素的引用以及一个用于在尾部增加链拉点的addLast()方法。

package dsaa.array;
/**
 * @(#)LinkList.java 2008-12-27 下午07:02:17
 * 
 * @author Qiu Maoyuan
 * Link List
 */
public class LinkList<E> {

	private Link first;
	private Link last;
	
	public void addFirst(E value){
		Link newElement = new Link(value);
		if(isEmpty()){
			last = newElement;
		}
		newElement.next = first;
		first = newElement;
	}
	
	public E getFirst(){
		if(isEmpty())
			throw new IllegalStateException("Linklist is empty");
		return first.element;
	}
	
	public boolean isEmpty(){
		return first == null;
	}
	
	public E removeFirst(){
		E value = getFirst();
		first = first.next;
		return value;
	}
	
	public boolean delete(E element){
		if(isEmpty())
			return false;
		Link current = first;
		Link previous = first;
		while(!element.equals(current.element)){
			if(current.next == null){
				return false;
			} else {
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		if(current == last)
			last = previous;
		return true;
	}
	
	public void addLast(E value){
		Link newElement = new Link(value);
		if(isEmpty()){
			first = newElement;
		}else{
			last.next = newElement;
		}
		last = newElement;
	}

	@Override
	public String toString(){
		StringBuilder buffer = new StringBuilder();
		Link current = first;
		while(current != null){
			buffer.append(current.toString());
			current = current.next;
		}
		return buffer.toString();
	}
	
	private class Link{
		
		private E element;
		
		private Link next;
		
		public Link(E element){
			this.element = element;
		}

		@Override
		public String toString(){
			return "[" + element.toString() + "]";
		}
	}
}

链表的效率
链表在表头的插入和删除操作都很快，只需要O(1)级别的时间。删除指定链接点的操作和数组一样，需要O(N)级别的时间。但是链表仍然比数组快得多，因为不需要像数组那样删除元素后还要移动元素。
链表比数组优越的另一个地方是：链表需要多少长度就可以分配多少长度，而数组的长度在创建时就是固定了的。尽管有Vector或者ArrayList这样可扩展长度的数组，但是它们只允许以固定的增量扩展，在内存的使用效率上还是比链表低。
下面是一个用链表实现的栈：

package dsaa.array;

import java.util.EmptyStackException;

/**
 * @(#)LinkStack.java 2008-12-28 上午04:21:08
 * 
 * @author Qiu Maoyuan
 * Stack
 */
public class LinkStack<E> {
	
	private LinkList<E> stackLinkList;
	
	public LinkStack(){
		stackLinkList = new LinkList<E>();
	}
	
	public void push(E value){
		stackLinkList.addFirst(value);
	}
	
	public E peek(){
		E element = null;
		try{
			element = stackLinkList.getFirst();



		}catch(IllegalStateException ex){
			throw new EmptyStackException();
		}
		return element;
	}
	
	public E pop(){
		E element = null;
		try{
			element = stackLinkList.removeFirst();
		}catch(IllegalStateException ex){
			throw new EmptyStackException();
		}
		return element;
	}
	
	public boolean isEmpty(){
		return stackLinkList.isEmpty();
	}
}

链表实现的队列：

package dsaa.array;
/**
 * @(#)LinkQueue.java 2008-12-28 上午04:27:07
 * 
 * @author Qiu Maoyuan
 * Link Queue
 */
public class LinkQueue<E> {
	
	private LinkList<E> queueLinkList;
	
	public LinkQueue(int size){
		queueLinkList = new LinkList<E>();
	}
	
	public E peek(){
		return queueLinkList.getFirst();
	}
	
	public void insert(E value){
		queueLinkList.addLast(value);
	}
	
	public E remove(){
		return queueLinkList.removeFirst();
	}
	
	public boolean isEmpty(){
		return queueLinkList.isEmpty();
	}
}

一写完代码发现链表是个好东西，Stack和Queue的实现变得很容易
在写这些笔记的代码时，我都采用TDD的方式，上一章写Stack和Queue的测试代码完全可以直接用在LinkStack和LinkQueue上。。。针对接口测试……嗯，也许一开始就应该对接口进行测试。

有序链表，就不多说了，看名字就知道意思了 插入元素的实现就是先遍历找准位置，然后把新增链接点的next指向previous的next（也就是current），再把previous的next指向新增的这个链接点。然后注意处理一下特殊情况（比如正好插入位置是在链表头）。有序链表的效率还是比数组高：插入时和数组一样只需要O(N)级别的查找时间，但插入之前不需要像数组那样移动元素。
下面是一个有序链表的实现：

package dsaa.array;
/**
 * @(#)SortedLinkList.java 2008-12-28 下午02:16:35
 * 
 * @author Qiu Maoyuan
 * Sorted LinkList
 */
public class SortedLinkList<E extends Comparable<E>> {

	private Link first;
	
	public void add(E value){
		Link newElement = new Link(value);
		if(isEmpty()){
			first = newElement;
		}else{
			Link current = first;
			Link previous = null;
			while(!endOfLink(current) && current.element.compareTo(value)>=0){
				previous = current;
				current = current.next;
			}
			if(!endOfLink(current)){
				newElement.next = current;
			}
			if(current == first)
				first = newElement;
			else
				previous.next = newElement;
		}
	}
	
	public E getFirst(){
		if(isEmpty())
			throw new IllegalStateException("Linklist is empty");
		return first.element;
	}
	
	public boolean isEmpty(){
		return first == null;
	}
	
	public E remove(){
		E value = getFirst();
		first = first.next;
		return value;
	}
	
	public boolean delete(E element){
		if(isEmpty())
			return false;
		Link current = first;
		Link previous = first;
		while(!element.equals(current.element)){
			if(endOfLink(current.next)){
				return false;
			} else {
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return true;
	}

	private boolean endOfLink(Link link) {
		return link == null;
	}

	@Override
	public String toString(){
		StringBuilder buffer = new StringBuilder();
		Link current = first;
		while(current != null){
			buffer.append(current.toString());
			current = current.next;
		}
		return buffer.toString();
	}
	
	private class Link{
		
		private E element;
		
		private Link next;
		
		public Link(E element){
			this.element = element;
		}

		@Override
		public String toString(){
			return "[" + element.toString() + "]";
		}
	}
}

给有序列表添加一个简单的带数组参数的构造方法，就可以用这个链表给一个数组进行排序，这种排序方法叫表插入排序法。表插入排序法的效率比数组插入排序法（第2章的插入排序法）还高些：构造有序链表时平均需要N^2/2次比较，时间复杂度为O(N^2)，跟数组插入排序法花在“比较”上的时间级别一样，但数组插入排序法花在复制上的时间级别为O(N)，而表插入排序法花在复制上的时间级别为O(N)。

package dsaa.array;
/**
 * @(#)SortedLinkList.java 2008-12-28 下午02:16:35
 * 
 * @author Qiu Maoyuan
 * Sorted LinkList
 */
public class SortedLinkList<E extends Comparable<E>> {

	private Link first;
	
	public SortedLinkList(){}
	
	public SortedLinkList(E[] array){
		for(E element : array){
			add(element);
		}
	}
	
	public void add(E value){
		Link newElement = new Link(value);
		if(isEmpty()){
			first = newElement;
		}else{
			Link current = first;
			Link previous = null;
			while(!endOfLink(current) && current.element.compareTo(value)>=0){
				previous = current;
				current = current.next;
			}
			if(!endOfLink(current)){
				newElement.next = current;
			}
			if(current == first)
				first = newElement;
			else
				previous.next = newElement;
		}
	}
	
	public E getFirst(){
		if(isEmpty())
			throw new IllegalStateException("Linklist is empty");
		return first.element;
	}
	
	public boolean isEmpty(){
		return first == null;
	}
	
	public E remove(){
		E value = getFirst();
		first = first.next;
		return value;
	}
	
	public boolean delete(E element){
		if(isEmpty())
			return false;
		Link current = first;
		Link previous = first;
		while(!element.equals(current.element)){
			if(endOfLink(current.next)){
				return false;
			} else {
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return true;
	}

	private boolean endOfLink(Link link) {
		return link == null;
	}

	@Override
	public String toString(){
		StringBuilder buffer = new StringBuilder();
		Link current = first;
		while(current != null){
			buffer.append(current.toString());
			current = current.next;
		}
		return buffer.toString();
	}
	
	private class Link{
		
		private E element;
		
		private Link next;
		
		public Link(E element){
			this.element = element;
		}

		@Override
		public String toString(){
			return "[" + element.toString() + "]";
		}
	}
}

可以这样使用这个有序链表：

	/**
	 * 表插入排序法
	 * @param <T>
	 * @param array
	 */
	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void listInsertionSort(T[] array){
		SortedLinkList linkList = new SortedLinkList(array);
		T[] newArray = (T[])new Comparable[array.length];
		for(int i=0; i<newArray.length; i++){
			newArray[i] = (T)linkList.remove();
		}
		array = newArray;
	}

[Java的泛型真恶心...... ]
还有一种链表叫双向链表，就是既可以向前遍历，又可以向后遍历的链表。这种链表的链接点内部有两个成员：previous和next。插入和删除的时候需要多操作一个引用。