链表
链表(Linked List)介绍 :
链表是有序的列表，但是它在内存中是存储如下
链表是以节点的方式来存储,是链式存储
每个节点包含 data 域， next 域：指向下一个节点.
如图：发现链表的各个节点不一定是连续存储.
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单向链表
单向链表存储节点思路图
单链表的应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
我们都知道 水浒传里有108位英雄吧
我们这里随便举例四个，我们想用链表的方式把他们放入我们的英雄榜里（单向链表）
新增，修改，删除的思路
添加英雄:
根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:
修改节点功能
古时候，有武功的人士逗喜欢为了排名去争斗，所以我们制作英雄榜需要有更换排名的功能
排名是固定的，他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可
先找到该节点，通过遍历，
temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
删除节点
这个功能呢可以理解为，有英雄不想争夺排名了，退休回家种田耕地享受生活了，我们需要把不需要位置的英雄占有的位置腾出来。
单向链表的增删改查
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.LinkedList * @className: LinkedlistDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/17 16:24 * @version: 1.0 */ public class LinkedlistDemo { public static void main(String[] args) { // 设置一些英雄对象 HeroNode heroNode = new HeroNode(1, "宋江", "及时雨"); HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星"); HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头"); // 声明单向链表 SingleLinkedlist linkedlist = new SingleLinkedlist(); //加入我们的英雄节点 //linkedlist.add(heroNode); //linkedlist.add(heroNode1); //linkedlist.add(heroNode2); //linkedlist.add(heroNode3); //加入按照编号 linkedlist.addByOrder(heroNode); linkedlist.addByOrder(heroNode3); linkedlist.addByOrder(heroNode2); linkedlist.addByOrder(heroNode1); //输出节点信息 linkedlist.List(); System.out.println("更新数据后"); linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师")); //输出节点信息 linkedlist.List(); System.out.println("删除数据后输出"); linkedlist.DeleteNode(1); linkedlist.List(); } } class SingleLinkedlist { //创建一个头结点 HeroNode head = new HeroNode(0, "", ""); //加入链表 public void add(HeroNode node) { //头节点不能动 这里我们用一个临时指针来记录 HeroNode temp = head; //遍历链表 while (true) { //遍历为空就代表找了最后一个节点 //不为空就后移一位继续找 if (temp.next == null) { break; } //没有找到最后就后移 temp temp = temp.next; } //跳出while证明找到了最后的节点，将我们的新节点加入到最后的节点的next即可 temp.next = node; } //添加节点 第二种方法 public void addByOrder(HeroNode node) { /* * 因为头结点不能动，我们通过指针来记录头节点来帮助找到添加的位置 *因为是单链表我们找的是 Temp是位于添加位置的前一个节点，否则插入不了 * */ //创建一个临时变量 HeroNode temp = head; //用来标识 英雄是否存在 默认为不存在（false） boolean flag = false; while (true) { //找到最后为空的位置 if (temp.next == null) { break; } //如果temp的下一个no 大于 我们加入的节点，就往temp加入 if (temp.next.No > node.No) { break; } //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点 else if (temp.next.No == node.No) { //将flag 修改为 true 代表已经存在 flag = true; break; } //如果上面的都没达成就代表当前节点位置不对，向后继续遍历 temp = temp.next; } // 判断 flag的值 if (flag) { //如果为 true 代表节点已经存在 System.out.printf("当前节点%d已经存在了，不能加入\n", node.No); } else { // 如果为false 那代表符合插入条件并且不存在与当前链表 node.next = temp.next; temp.next = node; } } //修改节点信息 public void updateNode(HeroNode newHeroNode) { if (head.next == null) { System.out.println("链表是空的"); } //这里是头节点不能修改，我用 temp 来指向头结点 HeroNode temp = head.next; // 是否找到了no的标识 boolean flag = false; while (true) { //找到最后一个 if (temp == null) { break; } if (temp.No == newHeroNode.No) { //如果等于 那么代表可以修改 flag = true; break; } temp = temp.next; } if (flag) { // true 修改信息 temp.NickName = newHeroNode.NickName; temp.Name = newHeroNode.Name; } else { System.out.printf("没有找到 %d 这个节点", newHeroNode.No); } } //删除节点信息 public void DeleteNode(int no) { HeroNode temp = head; // 用来标注 是不是可以删除 boolean flag = false; while (true) { if (temp.next == null) { break; } if (temp.next.No == no) { flag = true; break; } temp = temp.next; } //根据flag 删除Node if (flag) { //找到的话就删除，这里我们只需要指向空 GC会回收 temp.next = temp.next.next; } else { System.out.printf("要删除的 %d 没有找到", no); } } //遍历链表 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.next; } } } /** * 编写 水浒传英雄 节点 * 用于存放每个英雄的属性 * */ 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; } //方便输出语句输出 @Override public String toString() { return "HeroNode{" + "No=" + No + ", Name='" + Name + '\'' + ", NickName='" + NickName + '\'' + '}'; } }
链表使用效果
总结
我们这次制作了属于自己的英雄榜（单向链表）,我们收货了什么呢？
节点之间联系的思路
逐渐适应数据结构的一些思想
动手实
