单链表的简单实现

1、单链表的存储结构

/**
 * 单链表
 * @author fox
 *
 */
public class Node {
	private Object nodeValue;
	private Node nextNode;
	
	public Node() {
		nodeValue = null;
		nextNode = null;
	}
	
	public Node(Object item) {
		nodeValue = item;
		nextNode = null;
	}
	
	public Node(Object item, Node next) {
		nodeValue = item;
		nextNode = next;
	}

	public Object getNodeValue() {
		return nodeValue;
	}

	public void setNodeValue(Object nodeValue) {
		this.nodeValue = nodeValue;
	}

	public Node getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}
		
}

2、由于单链表是一种线性结构，所以他实现了LinearList接口。
关于LinearList接口，详情请查看http://fox-ed.iteye.com/blog/1775542
详细实现方法如下：

/**
 * 单链表的实现
 * @author fox
 *
 */
public class SingleLinkList implements LinearList {

	private Node head;
	public SingleLinkList() {
		head = null;
	}
	
	public SingleLinkList(Node node) {
		this.head = node;
	}
	
	public boolean isEmpty() {
		if(head == null) {
			return true;
		} else {
			return false;
		}
	}

	public int size() {
		int size = 0;
		Node temp = this.head;
		while(temp != null) {
			size++;
			temp = temp.getNextNode();
		}
		return size;
	}

	public Object get(int index) {
		checkIndex(index);
		Node temp = this.head;
		for(int i = 0; i < index; i++) {
			temp = temp.getNextNode();
		}
		return (Object)temp.getNodeValue();
	}

	public void set(int index, Object o) {
		checkIndex(index);
		Node node = this.head;
		for(int i = 0; i < index; i++) {
			node = node.getNextNode();
		}
		node.setNodeValue(o);
	}

	public boolean add(int index, Object o) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("下标错误:"+index);
		}
		
		if(head == null) {
			head = new Node(o);
		} else {
			Node temp = this.head;
			if(index == 0) {
				this.head = new Node(o,temp);
			} else {
				int i =0;
				while(temp.getNextNode() != null && i < index - 1) {
					i++;
					temp = temp.getNextNode();
				}
				temp.setNextNode(new Node(o,temp.getNextNode()));
			}
		}
		return true;
	}

	public boolean add(Object o) {
		return add(Integer.MAX_VALUE,o);
	}

	public Object remove(int index) {
		checkIndex(index);
		Object oldObj = null;
		Node temp = this.head;
		if(index == 0) {
			oldObj = (Object)head.getNodeValue();
			this.head = temp.getNextNode();
			temp = null;
		} else {
			int i = 0;
			while(temp.getNextNode() != null && i < index - 1) {
				i++;
				temp = temp.getNextNode();
			}
			Node node = temp.getNextNode();
			oldObj = (Object) node.getNodeValue();
			temp.setNextNode(node.getNextNode());
			node = null;
		}
		return oldObj;
	}

	public void clear() {
		int size = this.size();
		if(size != 0) {
			for(int i = size - 1;i >= 0; i--) {
				this.remove(i);
			}
		}
	}
	
	private void checkIndex(int index) {
		if(index < 0 || index > this.size() - 1) {
			throw new IndexOutOfBoundsException("下标错误:"+index);
		}
	}

}