package LinkList;

public class Node<T> {
	public T data;//数据域
	public Node next;//结点域
	
	//默认构造方法
	public Node(){
	}
	
	//带参构造方法,非头结点初始化
	public Node(T data,Node next){
		this.data=http://www.mamicode.com/data;>
************************************************华丽的分割线************************************************************************
package LinkList;
/**
 * ****************带头结点的单链表及其实现*********************
 * 
 * @author wl
 *
 */
public class SinglyLinkList<T> {
	Node<?> head;//头结点
	int size;//链表大小
	Node<?> current;//当前结点
	
	//初始化一个空链表
	public SinglyLinkList(){
		this.head=new Node<Object>(null);
		this.size=0;
		this.current=head;
	}
	
	//判断链表是否为空
	public boolean isEmpty(){
		return size==0;
	}
	//打印链表
	public void traverse(){
		if(isEmpty()){
			System.out.println("null");
		}else{
			for(Node<?> p=head.next;p!=null;p=p.next){
				System.out.print(p.data+",");
			}
			System.out.println();
		}
	}
	//从头结点增加结点
	public void addFromHead(T value){
		Node<T> node=new Node<T>(value,null);
		node.next=head.next;
		head.next=node;
		size++;
	}
	
	//从尾结点增加结点
	public void addFromTail(T value){
		Node<T> node=new Node<T>(value,null);
		this.current=head.next;
		
		if(current==null){
			head.next=node;
			size++;
		}else{
			while(current.next!=null){//将当前结点定位到尾结点
				current=current.next;
			}
			current.next=node;
			size++;
		}
	}
	
	//从头结点删除
	public void removeFromHead(){
		if(isEmpty()){//判断链表是否为空
			throw new RuntimeException("链表为空");
		}
		
		current=head.next;//当前结点
		head.next=current.next;
		current.next=null;
		size--;
	}
	
	//从尾结点删除
	public void removeFromTail(){
		if(isEmpty()){//判断链表是否为空
			throw new RuntimeException("链表为空");
		}
		
		Node<?> prev=null;//前一个结点
		this.current=head.next;
		while(current.next!=null){//将当前结点定位到尾结点
			prev=current;
			current=current.next;
		}
		prev.next=null;
		size--;
	}
	
	//在第index后面插入一个结点
	public void insert(int index,T value){
		if(index<0||index>size){
			throw new RuntimeException("参数index有误");
		}
		
		Node<T> node=new Node<T>(value,null);
		
		if(index==0){
			node.next=head.next;
			head.next=node;
			size++;
		}else{
			int count=0;//计数器
			Node<?> prev=null;//前一个结点
			current=head.next;
			while(current!=null&&count!=index){//将当前结点定位到第index个结点处
				prev=current;
				current=current.next;
				count++;
			}
		
			node.next=current;
			prev.next=node;
			size++;
		}
		
	}
	
	//删除任意位置index位置的某个结点
	public void remove(int index){
		if(index<0||index>size){
			throw new RuntimeException("参数index有误");
		}
		
		if(index==0){
			current=head.next;
			head.next=current.next;
			size--;
		}else{
			int count=0;//计数器
			Node<?> prev=null;//前一个结点
			current=head.next;
			while(current!=null&&count!=index){//将当前结点定位到第index个结点处
				prev=current;
				current=current.next;
				count++;
			}
		
			prev.next=current.next;
			current=null;
			size--;
		}
	}
	
	//根据value值删除结点，当有多个相同的value值时，只删除第一个
	public void removeByValue(T value){
		if(isEmpty()){
			throw new RuntimeException("链表为空");
		}
		
		int count=0;//计数器
		Node<?> prev=null;//前一个结点
		current=head.next;
		while(current!=null&¤t.data!=value){//将当前结点定位到值为value的第一个结点处
			prev=current;
			current=current.next;
			count++;
		}
		
		if(count>size){
			throw new RuntimeException("不存在值为value的结点");
		}
		
		prev.next=current.next;
		current=null;
		size--;
	}
}


Java数据结构系类之——链表（1）：单链表及相关常用操作