Java实现带头结点的单链表

链表的特点

1，以节点方式存储，是链式结构。

2，每个节点包含data域，next域：指向下一个节点。

3，链表的各个节点不一定是连续存储。

4，链表分为带头节点和不带头节点两种类型的链表。

代码实现：

//进行测试

public class SingleLinkedList
{
	public static void main(String[] args) 
	{//创建节点
		HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode h2 = new HeroNode(3, "卢俊义", "玉麒麟");
		HeroNode h3 = new HeroNode(4, "吴用", "智多星");
		HeroNode h4 = new HeroNode(2, "林冲", "豹子头");
		
	//创建给链表
	SingleLinkedListDemo s = new SingleLinkedListDemo();
	//加入
		s.add(h1);
		s.add(h2);
		s.add(h3);
		s.add(h4);
	s.list();	
	}
}
//定义一个SingleLinkedListDemo管理结点
class SingleLinkedListDemo
{ 
//初始化一个头节点，不要动
			private HeroNode head = new HeroNode(0,"","");
			//添加结点到单向链表，先找到当前链表的最后节点，再将最后结点的next指向新的结点。
			public void add(HeroNode node)
			{
			//先找出最后的一个节点，把新加的节点放在最后一个节点的后面
			//设置一个辅助遍历
			HeroNode temp = head;
			while(true)
			{
			if(temp.next==null){break;}
			temp=temp.next;//如果没有找到最后将temp后移
			}
			//当退出循环后temp就指向了链表的最后
			temp.next=node;
			}
//显示链表【遍历】
public void list()
{
	if(head.next==null)
	{
	System.out.println("链表为空！");
	return;
	}
	HeroNode temp = head.next;因为头结点不能动，所以需要一个辅助变量	
			while(true) {
			if(temp == null) {//判断是否到链表最后
				break;
			}
			//输出结点的信息
			System.out.println(temp);
			//将temp后移
			temp=temp.next;
}
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//如果有这个排名，则添加失败并给出提示
	public void addByOrder(HeroNode node) {
	//头结点依然不能动，因此我们仍然通过一个辅助指针来帮助找到添加节点、因为是单链表所以我们找的temp位于要添加位置的亲一个结点。
		HeroNode temp = head;
		boolean flag = false;
		while(true) {
			if(temp.next == null) {
				break;//表名链表已经在最后
			}
			if(temp.next.no>node.no) {//位置找到在temp后插入
				break;
			}else if(temp.next.no == node.no) {
				flag = true;//说明标号存在
				break;
			}
			temp = temp.next;//后移，继续遍历
		}
		if(flag) {//不能添加，说明标号存在
			System.out.println("编号"+node.no+"已经存在了！");
		}else {//插入到链表中，temp的后面
			node.next = temp.next;
			temp.next = node;
		}
		//修改结点信息，根据编号来修改，即no编号不能改
	public void update(HeroNode node ) {
			if(head.next == null) {
			System.out.println("链表为空！");
			return;
			//找到需要修改的结点，根据no编号
			//定义一个辅助变量			
		HeroNode temp = head.next;
		boolean flag = false;	//表示未找到该节点
		while(true) {
			if(temp == null) {//已经遍历完链表
				break;
			}
			if(temp.no == node.no) {
				flag = true;//找到
				break;
			}
			temp = temp.next;
		}//根据flag判断shifou找到要修改的结点
		if(flag) {
			temp.name = node.name;
			temp.nickname = node.name;
		}else {//没有找到
			System.out.println("不存在该节点！");
		}
		
		
}
//删除结点
//头结点依然不能动，因此我们仍然通过一个辅助指针来帮助找到添加节点、因为是单链表所以我们找的temp位于要添加位置的亲一个结点。
//我们早比较时，是temp.next.no和需要删除的结点的no比较

	public void del(int no) {
		if(head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		HeroNode temp = head;
		boolean flag = false;	
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.no == no) {
				flag = true;//找到待删除结点的前一个结点temp
				break;
			}
			temp = temp.next;//temp后移，遍历
		}
		if(flag) {//找到可以删除
			temp.next = temp.next.next;
		}else {
			System.out.println("该节点不存在！");
		}
		}	
}

class HeroNode{
	public int no;//英雄的编号
	public String name;//人名
	public String nickname;//绰号
	public HeroNode next;//下一个节点
	//构造器
	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	@Override
	//为了显示方便重写toString
	public String toString() {
	return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}	
}