本文共 6970 字,大约阅读时间需要 23 分钟。
链表是有序的列表,他在内存中如下存储
单链表(带头节点)的逻辑结构如下
创建:
遍历:
添加:
删除:
使用带头节点的单向链表实现水浒英雄排行榜管理,要求能完成对英雄人物的增删改查
package com.sisyphus.linkedlist;public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 HeroNode hero1 = new HeroNode(1,"宋江","及时雨"); HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟"); HeroNode hero3 = new HeroNode(3,"吴用","智多星"); HeroNode hero4 = new HeroNode(4,"林冲","豹子头"); //创建一个链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入// singleLinkedList.add(hero1);// singleLinkedList.add(hero2);// singleLinkedList.add(hero3);// singleLinkedList.add(hero4); //加入 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero3); //显示 singleLinkedList.list(); //测试修改节点的代码 HeroNode newHeroNode = new HeroNode(2,"小卢","小尾巴"); singleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况:"); singleLinkedList.list(); //查找一个节点 singleLinkedList.queryByName("小卢"); //删除一个节点 singleLinkedList.del(1); singleLinkedList.del(3); singleLinkedList.del(4); System.out.println("删除后的链表情况:"); singleLinkedList.list(); }}//定义SingleLinkedList 管理我们的英雄class SingleLinkedList{ //先初始化一个头节点,头节点不能动,否则会找不到这个链表 private HeroNode head = new HeroNode(0,"",""); //添加节点到单向链表 //当不考虑编号顺序时: //1。找到当前链表的最后节点 //2。将最后这个节点的 next 指向新的节点 public void add(HeroNode heroNode){ //因为 head 节点不能动,因此我们需要一个辅助变量 temp HeroNode temp = head; //遍历链表,找到链表的尾部 while(true){ if (temp.next == null){ break; } //如果不是最后一个节点,将 temp 后移 temp = temp.next; } //当退出 while 循环时,temp 就指向了链表的最后 //将最后这个节点的 next 指向新的节点 temp.next = heroNode; } //根据排名将英雄插入到指定位置 //(如果已有这个排名,则添加失败,并给出提示) public void addByOrder(HeroNode heroNode){ //因为头节点不能动,因此我们仍借助辅助变量来找到添加的位置 //我们要找位于添加位置的前一个节点 HeroNode temp = head; boolean flag = false; //表示添加的编号是否存在,默认为 false while (true){ if (temp.next == null){ //说明temp已经在链表的最后 break; } if (temp.next.no > heroNode.no){ //位置找到,在 temp 后面一个位置插入 break; }else if (temp.next.no == heroNode.no){ //说明编号存在 flag = true; //编号存在 break; } temp = temp.next; //后移,也就是遍历当前列表 } //判断 flag 的值 if (flag){ //说明编号存在,不能添加 System.out.printf("准备插入的英雄编号 %d 已经存在,不能添加\n",heroNode.no); }else{ //插入到链表中,temp 的后面 heroNode.next = temp.next; temp.next = heroNode; } } //修改节点的信息,根据编号来修改,即编号不能修改 //说明 //1.根据 newHeroNode 的 no 来修改即可 public void update(HeroNode newHeroNode){ //判断是否为空 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 == newHeroNode.no){ //找到了 flag = true; break; } temp = temp.next; } //根据 flag 判断是否找到要修改的节点 if (flag){ temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; }else{ //没有找到 System.out.printf("没有找到编号 %d 的节点",newHeroNode.no); } } //删除节点 //思路 //1。head 不能动,因此我们需要一个 temp 辅助变量找到待删除节点的前一个节点 //2。我们在比较时,是 temp.next.no 和需要删除的节点的 no 比较 public void del(int no){ HeroNode temp = head; boolean flag = false; //表示是否找到待删除节点 while(true){ if (temp.next == null) { //已经到链表的尾部 break; } if (temp.next.no == no){ //找到待删除节点的前一个节点 temp flag = true; break; } temp = temp.next; //后移继续遍历 } //判断flag if (flag){ //找到 //可以删除 temp.next = temp.next.next; }else{ System.out.printf("要删除的 %d 节点不存在\n",no); } } //展示链表 //借助temp辅助变量,遍历整个链表 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 queryByName(String name){ //判断链表是否为空 if(head.next == null){ System.out.println("链表为空"); return; } HeroNode temp = head.next; boolean flag = true; //表示是否找到对应节点 while (true){ //判断是否在链表的尾部 if (temp == null){ break; } if (temp.name == name){ flag = false; System.out.println("查询成功:"); System.out.println(temp); break; } temp = temp.next; } if (flag){ System.out.println("链表中没有对应节点!"); } }}//定义 HeroNode,每个 HeroNode 对象就是一个节点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; } //为了显示方法,我们重新 toString @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + '}'; }}
思路:
思路:
转载地址:http://ejyki.baihongyu.com/