java 单向链表

   链表是由一个又一个的节点组成的，每个节点都包括节点值以及下一个节点的存储地址。
   首先先看节点类

package test; 
/** 
 * @author Marospring
 * @version 创建时间：2012-7-25 上午11:46:23 
 * 单链表节点 
 */
public class LinkNode {
	public char value;
	public LinkNode next;
	
	
}

这是一个节点类，为了表述方便，这里我没有写setter和getter，直接将属性设置成public，在操作节点的时候直接用“=”，这里可以理解为指向的意思。下面先看图再看代码。

package test; 


/** 
 * @author Marcospring 
 * @version 创建时间：2012-7-25 上午11:46:41 
 * 单链表
 */
public class LinkedList{
	private LinkNode head;
	private LinkNode tail;
	private int size;

	public LinkedList(){
		this.size = 0;
	}
	
	//添加元素
	public void add(char c){
		LinkNode node = new LinkNode();
		node.value = c;
		if(size == 0){
			//如果链表为空则将头节点和尾节点都指向新加入的节点
			head = node;
			tail = node;
		}else{
			//如果不为空，则先将为加入新节点前的为节点的next指向新节点，然后将尾元素赋值为新节点
			tail.next = node;
			tail = node;
		}
		size++;
	}
	//在指定位置添加元素
	public void add(int index,char c){
		LinkNode node = new LinkNode();
		node.value = c;
		LinkNode temp = new LinkNode();
		temp = head;
		//寻找要加入节点的位置，要找到加入位置的前一个节点。
		for(int i=0;i<index-1;i++){
			temp = temp.next;
		}
		//将要添加节点的next指向找到节点的next
		node.next = temp.next;
		//将找到节点的next指向新加入的节点。
		temp.next = node;
		size++;
	}
	//删除指定位置的元素
	public void remove(int index){
		LinkNode temp = new LinkNode();
		temp = head;
		//找到要删除元素的前一个节点
		for(int i = 0;i<index-1;i++){
			temp = temp.next;
		}
		//要删除节点的前一个元素的next指向它的下下个元素
		temp.next = temp.next.next;
		size--;
	}
	//清空链表
	public void clear(){
		head =null;
		tail = null;
		size = 0;
	}
	//是否包含某元素
	public boolean contain(char c){
		LinkNode temp = new LinkNode();
		temp = head;
		for(int i=0;i<size-1;i++){
			if(temp.value == c){
				return true;
			}else{
				temp = temp.next;
			}
		}
		return false;
	}
	//链表大小
	public int size(){
		return size;
	}
	//获得制定位置元素
	public char get(int index){
		LinkNode node = new LinkNode();
		node = head;
		if(index > size){
			//这里可以拋异常，我选择打印，然后返回“！”
			System.out.println("您访问的元素不存在！");
			return '!';
		}else{
			for(int i=0;i<index-1;i++){
				node = node.next;
			}
			return node.value;
		}
	}
	//展示链表
	public void display(){
		LinkNode node = new LinkNode();
		node = head;
		for(int i = 0;i<size;i++){
			System.out.print(node.value+",");
			node = node.next;
		}
	}
}

这里要注意的是在指定位置添加节点的这个方法，如果先将找到节点的next指向新加入的节点，然后再将新加入节点的next指向找到节点的next会出现什么情况呢？