单向链表总结

 单向链表：形象点就是以上那个鬼东西！

 

         它是由一系列的节点串联成的。

 

          而在其节点中包含两部分：1.数据域   2.下一个节点

 

          而下一个节点的能使节点串联的关键

 

          以下是节点的内容：

//  <T>  表示泛型
public class Node <T> {
	
	//数据域
	public T data;
	//下一个节点
	public Node next;
	//构造函数
	Node(T data)
	{
		super();
		this.data=data;
	}

}

 

而这里的下一个节点相当于c++中的指针，它指向下一个节点！

 

      以下是链表的一些功能实现，并添加了详细的注释：

 

        （特别注意的是有一些功能的实现要将第一个节点分开独立判断的！）

 

public class Link <T> {
	
	//头节点
	private Node head;
	//尾节点
	private Node tail;
	//大小
	private int size=0;
	
	
	//添加元素
	public void add(T elem)
	{
		Node node = new Node(elem);
		//添加第一个节点，头尾节点都是（指向）它
		if(size==0)
		{
			head=node;
			tail=node;
		}
		else
		{ 
			//尾节点的下一个指向新的节点
			tail.next=node;
			//新的节点变成尾节点
			tail=node;
		}
		size++;
	}
	//去除某位置的元素
	public void remove(int index)
	{
		Node last=head;
		//判断是否为第一个节点
		if(index==0)
		{
			head=last.next;
			last=null;
		}
		else if(index>0&&index<size){
			//遍历找到index位置的节点、它的上一个节点和它的下一个节点
			for(int i=0;i<index-1;i++)
			{
				last=last.next;
			}
			//index位置的节点    node
			Node node=last.next;
			//node的下一个节点   nextNode
			Node nextNode=node.next;
			//node上一个节点跳过node指向node的下一个节点
			last.next=nextNode;
			//node 指向空
			node.next=null;
		}
		size--;
	}
	//
	public T remove2(int index)
	{
		if(index<0||index>=size||size==0)
			return null;
		size--;
		if(index==0)
		{
			Node node=head;
			head=node.next;
			node=null;
			if(size==0)
			{
				tail=null;
			}
			return (T)node.data;
		}else{
			Node last=head;
			for(int i=0;i<index-1;i++)
			{
				last=last.next;
			}
			Node node=last.next;
			Node nextNode=node.next;
			
			last.next=nextNode;
			node.next=null;
			
			
			if(index==size-1)
			{
				tail=last;
			}
			
			return (T)node.data;
		}
	}
	//改变某位置的data
	public void change(int index,T elem)
	{
		Node last=head;
		//同样，判断是否为第一个
		if(index==0)
		{
			last.data=elem;
		}
		else if(index>0&&index<=size){
			//遍历找到index位置的节点
			for(int i=0;i<index-1;i++)
			{
				last=last.next;
			}
			//找到node
			Node node=last.next;
			//将elem赋值给它的数据域
			node.data=elem;
		}
	}
	//查询某个值在链表中的位置
	public void find(T elem)
	{
		//index记录节点位置
		int index=0;
		//判断是否有要查的元素的标志
		int flag=0;
		//遍历
		for(Node node =head;node!=null;node=node.next)
		{
			//找到元素
			if(node.data==elem)
			{
				//输出位置
				System.out.println("index="+index);
				//完成有盖元素的判断
				flag=1;
			}
			index++;
		}
		//有无该元素？
		if(flag==0)
			System.out.println("该链表中无此元素");
	}
	//查找某个位置的值
	public T find(int index)
	{
		if(index<0||index>size||size==0)
			return null;
		Node node=head;
		for(int i=0;i<index;i++)
		{
			node=node.next;
		}
		return (T)node.data;
	}
	//插入
	public void insert(int index,T elem)
	{
		if(index==0)
		{
			Node newNode = new Node(elem);
			newNode.next=head;
			head=newNode;
		}
		else{
			Node last = head;
			for(int i=0;i<index-1;i++)
			{
				last=last.next;
			}
			Node node=last.next;
			Node newNode=new Node(elem);
			last.next=newNode;
			newNode.next=node;
		}
	}
	
	//输出链表
	public void showInfo()
	{
		//判断
		if(size>0)
		{
			//遍历输出元素
			for(Node node=head;node!=null;node=node.next)
			{
				System.out.print(node.data+"  ");
			}
		}
		System.out.println();
	}
	//递归法输出链表
	public void showInfo2(Node node)
	{
		if(size>0){
			//输出
			System.out.print(node.data+"  ");
			//递归调用
			if(node.next!=null)
				showInfo2(node.next);
		}
	}
	//为了方便重载函数（因为head类型为private）
	public void showInfo2()
	{
		showInfo2(head);
		System.out.println();
	}
	
	public int getSize()
	{
		return size;
	}
	
	public static void main(String [] args)
	{
		Link<Integer> link=new Link<Integer>();
		for(int i=0;i<10;i++)
		{
			link.add(i);
		}
		link.showInfo();
//		System.out.println("size="+link.getSize());
//		link.remove(123);
//		link.showInfo();
//		link.change(3, 100);
//		link.showInfo();
//		link.find(1000);
		link.insert(0, 1000);
		link.showInfo2();
		System.out.println(link.find(3));
	}
	
}