前言

链表

链表(Linked List)介绍 :

链表是有序的列表，但是它在内存中是存储如下

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含 data 域， next 域：指向下一个节点.
3. 如图：发现链表的各个节点不一定是连续存储.
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单向链表

单向链表存储节点思路图

单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作

我们这里随便举例四个，我们想用链表的方式把他们放入我们的英雄榜里（单向链表）

添加英雄:

根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:

修改节点功能

古时候，有武功的人士逗喜欢为了排名去争斗，所以我们制作英雄榜需要有更换排名的功能

排名是固定的，他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可

• 先找到该节点，通过遍历，
• 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 + '\'' +
                '}';
    }
}

总结

我们这次制作了属于自己的英雄榜（单向链表）,我们收货了什么呢？

• 节点之间联系的思路
• 逐渐适应数据结构的一些思想
• 动手实