链表 Linked List

链表 Linked List

目录
  • 链表介绍
  • 单链表
    • 单链表的应用实例
      • 添加-直接添加到末尾
      • 添加-顺序添加
      • 更新
      • 删除
    • 单链表的面试题
  • 双链表

链表介绍

  • 链表时有序的列表,但是它在内存中是存储如下
    image

小结

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

单链表

单链表(带头节点)逻辑示意图
image

单链表的应用实例

使用带 head头的单向链表实现水浒传英雄排行榜,管理

  1. 完成对英雄任务的增删改查操作,注:删除和修改,查找
  2. 第一种方式在添加英雄时,直接添加到链表的尾部,
  3. 第二种方时在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)

单链表的创建示意图(添加),显示单向链表的分析
image

添加-直接添加到末尾

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(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        //显示一把
        singleLinkedList.list();
    }
}

//定义 SingleLinkedListDemo 管理我们的英雄
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.next;
        }
        //当退出 while循环时,temp就指向链表的最后
        //将最后这个节点的 next,指向新的节点
        temp.next = heroNode;
    }

    //显示链表 遍历
    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;
        }
    }
}

//定义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  next就不要显示了
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name="" + name + """ +
                ", nickname="" + nickname + """ +
                "}";
    }
}

添加-顺序添加

image

    //第二种方时在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)
    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助我们找到添加的位置
        //因为单链表,因为我们找到的temp,是位于 添加位置的前一个界定啊,否则插入不了
        HeroNode temp = head;
        boolean flag = false;//flag 标志添加的编号是否存在,默认为false
        while (true) {
            if (temp.next == null) {//说明 temp已经在链表的最后
                break;//无论如何都要退出
            }
            if (temp.next.no > heroNode.no) {//位置找到,就在 temp的后面插入
                break;

            } else if (temp.next.no == heroNode.no) {//说明希望添加的 heroNode的编号依然存在
                flag = true;//说明编号存在
                break;
            }
            //如果上面的都没有成立 temp要后移,遍历当前链表
            temp = temp.next;
        }
        //判断 flag的值
        if (flag) {//不能添加,说明编号已经存在
            System.out.println("准备插入的英雄的编号" + heroNode.no + "已经存在不能添加");
        } else {
            //插入到链表中 temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

更新

思路:

  1. 先找到该节点,通过遍历
  2. temp.neme = newHeroNode.name;
    temp.nickname = newHeroNode.nickname;
    //说明
    //修改节点的信息,根据no编号修改,即 no编号不能修改
    //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.println("没有找到编号" + newHeroNode.no + "的节点,不能修改");
        }
    }

删除

image

    //删除节点
    //思路
    //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 = temp.next;
        }
        //判断 flag
        if (flag) {
            //可以删除
            temp.next = temp.next.next;
        } else {//未找到该节点
            System.out.println("找删除的" + no + "节点未找到");
        }

    }

单链表的面试题

  1. 求单链表中有效节点的个数
  2. 查找单链表中的倒数第k个结点 【新浪面试题】
  3. 单链表的反转【腾讯面试题,有点难度】
  4. 从尾到头打印单链表 【百度,要求方式1:反向遍历 。 方式2:Stack栈】
  5. 合并两个有序的单链表,合并之后的链表依然有序

双链表