链表的Java实现

一 、链表介绍

链表（Linked List)，是有序列表

• 链表是以结点的方式来存储的
• 每个结点包含data域和next域
• 链表的各个节点不一定是连续存放的
• 链表分带头结点的链表和没有头结点的链表

1.1 单链表

1.1.1单链表的应用实例

水浒英雄排行榜

1.1.2单链表实现在链表尾部添加节点

• 按照顺序添加，每个新节点添加到链表的尾部

//定义一个HeroNode ，每个HeroNode对象就是一个节点

class HeroNode {
	public int no;
	public String name;
	public String nickname;
	public HeroNode next;
	
	//构造器
	public HeroNode(int hNo,String hName,String hNickName) {
		this.no = hNo;
		this.name = hName;
		this.nickname = hNickName;
	}
	//重写toString方法
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

//定义一个SingleLinkedList管理英雄
class SingleLinkedList1{
	//初始化一个头结点
	private static final HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路：当不考虑编号顺序时，找到当前链表的最后一个节点，将最后一个节点的next指向新的节点
	public void add(HeroNode heroNode) {
		//遍历链表找到最后一个节点
		//退出循环时temp指向最后一个节点
		HeroNode temp = head;
		while(true) {
			if(temp.next == null) {
				break;
			}
			temp = temp.next; 
		}
		temp.next = heroNode;	
	}
	//显示链表
	public void showList() {
		//先判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		while(true) {
			if(temp == null) {
				break;
			}
			//输出节点信息
			System.out.println(temp.toString());
			temp = temp.next;
		}
	}
}

1.1.3 单链表实现在指定位置插入结点

• 在SingleLnkedLIst1类中添加新的方法：

//第二种添加方式：在指定位置添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;
		boolean flag = false;
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.no>heroNode.no) {
				break;
			}
			if(temp.next.no == heroNode.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			System.out.println("该排行已经有英雄！不能添加");
			return;
		} else {
			heroNode.next = temp.next;
			temp.next = heroNode;	
		}
	}

1.1.4 单链表实现节点的修改

//根据NO编号来修改信息
	public void update(HeroNode heroNode,String name,String nickname) {
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp == null) {
				break;
			}
			if(temp.no == heroNode.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			temp.name = name;
			temp.nickname = nickname;
		} else {
			System.out.println("没有找到该节点" );
		}
	}

1.1.5 单链表实现节点的删除

public void deleteNode(HeroNode heroNode) {
	HeroNode temp = head;
	if(temp == null) {
		System.out.println("链表空");
		return;
	}
	boolean flag = false;
	while(true) {
		if(temp.next.no == heroNode.no) {
			flag = true;
			break;
		}
		if(temp.next == null) {
			break;
		}
		temp = temp.next;
	}
	if(flag) {
		temp.next = temp.next.next;
		return;
	}
}

1.2 双向链表