java实现单向链表

一切皆为对像，链表本是可以看成一个对像，链表的结点同样也可以看成一个对像。

自定义异常类：

public class MyException extends Exception {
	
	public MyException(){};
	
	public MyException(String msg){
		super(msg);
	}

}

链表结点对像：

public class Node {

	public Node next=null;
	public Object value=null;
	
	Node(Object value){
		this.value=value;
	}	
}

链表对像：

public class SinglyLinked {
	
	private Node head=null;
	
	SinglyLinked(){
		
	}
	/**
	 * 获取链表头元素
	 * @return 链表头结点
	 * @throws MyException 
	 */
	public Node getHead() throws MyException{
		if(head==null){
			throw new MyException("链表为空");
		}
		return head;
	}
	/**
	 * 获取该结点下的下一个结点
	 * @param node
	 * @return 
	 */
	public Node getNext(Node node){
		return node.next;
	}
	/**
	 * 判断该结点是否还有下一个结点
	 * @param node
	 * @return
	 */
	public boolean hasNext(Node node){
		
		if(node.next==null){
			return false;
		}
		return true;
	}
	/**
	 * 获得链表的最后一个元素
	 * @return
	 * @throws MyException 
	 */
	public Node getLast() throws MyException{
		
		Node curNode=null;
		Node next=null;
		
		if(head==null){
			throw new MyException("链表为空");
		}else{
			curNode=head;
			while(hasNext(curNode)){
				next=curNode.next;
				curNode=next;
			}
		}
		return curNode;
	}
	/**
	 * 根据索引获得元素
	 * @param index
	 * @return
	 */
	public Node getNode(int index)throws MyException{
		
		Node node=null;
		Node curNode=null;
		Node next=null;
		
		if(head==null){
			throw new MyException("链表为空");
		}else{
			curNode=head;
			for(int i=0;i<index;i++){
				if(curNode==null){
					throw new MyException("你要查找的元素索引超过了链表的长度");
				}
				node=curNode;
				if(hasNext(curNode)){
					next=curNode.next;
					curNode=next;
				}else{
					curNode=null;
				}
			}
		}
		return node;
	}
	/**
	 * 在链表头添加结点
	 * @param node
	 */
	public void addFirst(Node node){
		if(head==null){
			head=node;
		}else{
			Node next=head;
			node.next=next;
			head=node;
		}
	}
	/**
	 * 在链表尾部添加元素
	 * @param node
	 * @throws MyException 
	 */
	public void addLast(Node node) throws MyException{
		
		if(head==null){
			head=node;
		}else{
			Node last=this.getLast();
			last.next=node;
		}
	}
	/**
	 * 在链表中间插入元素
	 * @param index 要插入的结点
	 * @param node
	 */
	public void insertNode(int index,Node node)throws MyException{
		
		Node prevNode=null;
		
		try{
			prevNode=getNode(index-1);
		}catch(MyException rex){
			rex.printStackTrace();
			throw new MyException("插入结点的索引大于链表长度");
		}

		if(hasNext(prevNode)){
			Node next=prevNode.next;
			prevNode.next=node;
			node.next=next;
		}else{
			prevNode.next=node;
		}

	}
	/**
	 * 删除链表的第一个元素
	 * @return
	 */
	public Node deleteFirst(){
		Node first=null;
		Node node=head.next;
		first=head;
		head=node;
		return first;
	}
	/**
	 * 删除链表的最后一个元素
	 * @return
	 */
	public Node deleteLast(){
		
		Node last=null;
		Node curNode=head;
		Node next=null;
		boolean flag=true;
		
		if(!hasNext(head)){
			head=null;
		}else{
			while(flag){
				next=curNode.next;
				if(hasNext(next)){
					curNode=next;
				}else{
					curNode.next=null;
					last=next;
					flag=false;
				}
			}
		}
		return last;
	}
	/**
	 * 按照索引删除元素
	 * @param index
	 * @return
	 */
	public Node deleteNode(int index)throws MyException{
		Node prevNode=null;
		try{
			prevNode=getNode(index-1);
		}catch(MyException mex){
			mex.printStackTrace();
			throw new MyException("你要删除的结点索引大于链表的长度");
		}
		Node node=null;

		if(hasNext(prevNode)){
			node=prevNode.next;
			if(hasNext(node)){
				Node next=node.next;
				prevNode.next=next;
			}else{
				prevNode.next=null;
			}
		}else{
			throw new MyException("你要删除的结点索引大于链表的长度");
		}

		return node;
	}	

}

评论

1 楼 finallygo 2010-07-02  

这个好像不支持环吧?