双向链表的实现与环形链表解决约瑟夫问题

双向链表、环形链表解决约瑟夫问题

双向链表

之前在 学会用Java实现一个单向链表 博客中已经介绍过单向链表

双向链表的区别在于,每一个节点不光有指向下一个节点的指针,也有指向上一个节点的指针

相比较而言,双向链表的好处在于,遍历时有前驱有后继,可进可退;缺点在于增加、删除节点时步骤更多了,每个节点也需要多分配一个指针的存储空间

用Java实现双向链表

实现双向链表,和单向链表很相似,区别在于节点对象多一个指向前一个节点的指针,同时增加、删除节点的操作多了几个步骤;而遍历、修改几乎没有区别

还是用梁山好汉的例子;首先创建单个节点对象

/**
 * 定义一个HeroNode2对象,就是一个双向链表中的节点
 */
class HeroNode2{

    /**
     * 英雄排名
     */
    public int no;
    /**
     * 名字
     */
    public String name;
    /**
     * 称号
     */
    public String nickname;
    /**
     * 指向下一个英雄
     */
    public HeroNode2 next;
    /**
     * 指向上一个英雄
     */
    public HeroNode2 pre;

    /**
     * 构造器 创建一个梁山好汉
     * @param no 排名
     * @param name 姓名
     * @param nickname 称号
     */
    public HeroNode2(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 + '\'' +
                '}';
    }
}

然后,DoubleLinkedList类表示一个带头结点的双向链表

添加上增删改查的方法

添加和删除时,需要考虑好前后关系,最多可能影响到四个指针

具体可阅读代码中的注释加以理解

/**
 * 双向链表类
 */
class DoubleLinkedList{

    /**
     * 先初始化一个头节点,头节点不动,也不存放具体数据
     */
    private final HeroNode2 head = new HeroNode2(0,"","");

    /**
     * 根据编号从双向链表中删除节点
     * @param no 要删除的节点编号
     */
    public void delete(int no){
        //遍历,让指针始终指向要遍历的节点
        HeroNode2 temp = head.next;
        while (temp!=null){
            //判断当前遍历的节点是否是要删除的节点,如果是进行删除,给出删除成功提示,并结束方法,如果不是继续遍历下一个
            if (temp.no == no) {
                //将上一个的下一个指向要删除的下一个
                temp.pre.next = temp.next;
                //这里需要判断如果要删除的不是最后一个,将下一个的上一个指向要删除的上一个
                if (temp.next!=null){
                    temp.next.pre = temp.pre;
                }
                System.out.println("删除成功");
                return;
            }
            temp = temp.next;
        }
        //退出循环后还没有结束,表示没有找到要删除的节点
        System.out.println("未找到要删除的节点"+no);
    }

    /**
     * 根据编号,修改节点,编号不能修改
     * @param newHeroNode 修改后的英雄信息
     */
    public void update(HeroNode2 newHeroNode){
        //1.遍历链表,找到要修改的编号no对应的节点
        HeroNode2 temp = head.next;
        while (temp != null){
            //有节点等待遍历,判断no是否相同
            if (temp.no == newHeroNode.no){
                //相同进行修改,打印修改成功提示,并直接结束方法
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                System.out.println("修改成功");
                return;
            }
            //不相同继续遍历下一个
            temp = temp.next;
        }
        //全部遍历完都没有成功修改退出方法,表示没有找到要修改的编号
        System.out.println("未找到编号"+newHeroNode.no+"的英雄,如有需要请直接填加");
    }

    /**
     * 添加节点到双向链表(添加到尾部)
     */
    public void add(HeroNode2 heroNode){
        //找到当前链表最后一个节点,把next指向这个新的节点
        //遍历链表的临时变量,指向当前正遍历到的节点,从head开始
        HeroNode2 temp = head;
        //判断当前temp是否存在next不存在说明当前temp指向的节点就是最后一个节点
        while (temp.next != null) {
            //存在就会进入循环,继续遍历,将temp指向当前temp的next
            temp = temp.next;
        }
        //当退出了循环之后,当前temp就是当前链表最后一个节点,将他的next指向正在新增的节点,将新增的pre指向temp
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    /**
     * 添加节点到双向链表(该方法会按排名的顺序排序)
     */
    public void addByOrder(HeroNode2 heroNode){
        //找到当前链表最后一个节点,把next指向这个新的节点
        //遍历链表的临时变量,指向当前正遍历到的前一个节点,从head开始
        HeroNode2 temp = head;
        //判断当前temp是否存在next不存在说明当前temp指向的节点就是最后一个节点
        while (temp.next != null) {
            //存在就会进入循环,先判断排名关系。如果和遍历到的节点排名和新插入的相同,抛出异常提示
            if (temp.next.no == heroNode.no){
                throw new RuntimeException("不能插入排名相同的节点");
            }
            //如果遍历到的节点排名大于当前插入节点的排名,说明新节点刚好应该在上一个节点和正在遍历的节点之间,执行插入操作后返回结束方法
            if (temp.next.no > heroNode.no){
                //当前插入节点的下一个指向当前遍历到的第一个比他排名高的节点
                heroNode.next = temp.next;
                //当前插入节点的前一个指向当前遍历节点的前一个
                heroNode.pre = temp;
                //将当前遍历节点的前一个的下一个指向当前插入的节点
                temp.next = heroNode;
                //将当前遍历节点的前一个指向当前插入的节点
                temp.next.pre = heroNode;
                return;
            }
            //如果排名比正在遍历的大说明还需要继续遍历,将temp指向当前temp的next进行下一次循环
            temp = temp.next;
        }
        //当退出了循环之后还没有找到应该存放的位子,当前temp.next为空temp就是当前链表最后一个节点
        //将他的next指向正在新增的节点
        temp.next = heroNode;
        //将新增的节点pre指向最后一个节点
        heroNode.pre = temp;
    }

    /**
     * 显示链表【遍历】
     */
    public void show(){
        System.out.println("----------------------------------------------");
        //先判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //遍历链表的临时变量,指向当前正遍历到的节点,从head的next开始,也就是从第一个开始
        HeroNode2 temp = head.next;
        //当前正遍历到的节点不为空的时候,打印当前节点,并将temp指向next继续参与遍历,直到temp为空表示遍历结束
        while (temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
        System.out.println("----------------------------------------------");
    }

}

环形链表解决约瑟夫问题

约瑟夫问题:

设编号为1,2,3...n的n个人围坐一圈

约定编号为k(1<=k<=n)的人从1开始报数,数到m的人出列,从下一个人开始继续从1报数,数到m再出列,依次类推,直到所有人都出列,由此产生一个出队编号的序列

分析:围坐一圈的人,报数只朝一个方向,那么如果将一个单向链表首尾相连,即可模拟出这一场景

然后开始遍历这个环形链表,找到要出列的人记录下来,然后从链表中删除,再从下一个人开始继续遍历,直到链表为空,即解决了这个问题

这个问题中,围坐的人作为链表中的节点对象,只需要一个编号no属性,和一个指向下一节点的指针即可

创建出Boy类

/**
 * boy类表示一个环形链表中的节点对象
 */
class Boy{

    /**
     * 编号
     */
    private int no;
    /**
     * 指向下一个节点,默认null
     */
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

}

还需要一个类来表示环形链表

需要用到两个指针,一个指向第一个节点一个指向最后一个节点

需要一个属性来记录当前链表中总节点数(剩余围坐人数)

指向第一个节点的指针用于确定开始遍历的位置,指向最后一个节点的指针用于判断遍历是否结束,否则环形链表的遍历会成为死循环

创建一个类SingleCircleLinkedList,表示环形链表

1.构造器根据一圈围了多少人,初始化一个包含了多少个Boy节点的环形链表

2.方法showList(),打印当前链表

3.方法countBoy(int startNo,int countNo),打印出圈顺序

/**
 * 创建单向环形链表类
 */
class SingleCircleLinkedList{

    //创建一个first节点,指向第一个节点,初始为空
    private Boy first = null;
    //创建一个last节点,指向最后一个节点,初始为空
    private Boy last = null;
    private int nums = 0;

    /**
     * 添加小孩节点
     * (尾插法,只能作为创建使用)
     *
     * @param nums 添加的小孩数量
     */
    public SingleCircleLinkedList(int nums){
        //对nums做入参校验,最少需要一个节点
        if (nums<1){
            System.out.println("创建环形链表至少需要1个节点");
            return;
        }
        //创建环形链表
        //至少创建一个节点,而且第一个节点需要区别对待,那就先创建出来,直接新建编号1节点让指针first指向第一个节点
        first = new Boy(1);
        //自己指向自己,形成环状
        first.setNext(first);
        //将最后一个也指向当前节点
        last = first;
        //然后再循环插入后续节点
        for (int i = 2; i <= nums; i++) {
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //如果不是第一个节点,将最后一个节点的next指向新节点,新节点的next指向first节点,再将最后一个节点更改为指向新节点
            last.setNext(boy);
            boy.setNext(first);
            last = boy;
        }
        //保存一下环形链表总节点数量
        this.nums = nums;
    }

    /**
     * 打印出循环链表的情况
     */
    public void showList(){
        //判断环形链表是否为空
        if (nums==0){
            System.out.println("当前链表为空");
            return;
        }
        //打印链表节点总数
        System.out.println("当前链表总节点数为:"+nums);
        //构建字符串作为最终的打印
        StringBuilder builder = new StringBuilder();
        //创建辅助指针遍历打印链表
        Boy curBoy = first;
        while (curBoy!=last){
            builder.append(curBoy.getNo()).append(" ").append("--> ");
            curBoy = curBoy.getNext();
        }
        //退出循环时说明辅助指针已经指向了最后一个,打印最后一个指向第一个即可
        builder.append(curBoy.getNo()).append(" ").append("--> ").append(curBoy.getNext().getNo());
        System.out.println(builder);
    }

    /**
     * 打印出圈顺序
     * @param startNo 从几号开始数
     * @param countNo 数几个出列
     */
    public void countBoy(int startNo,int countNo){
        //判断链表是否为空
        if (nums==0){
            System.out.println("链表为空");
            return;
        }
        //数据校验,只能从1到nums开始报数
        if (startNo<1 || startNo>nums) {
            System.out.println("开始报数人不存在与链表中");
            return;
        }
        //校验结束,创建一个辅助指针帮助遍历计算小孩出圈
        Boy helper = first;
        //先找到开始节点,用helper指向
        while (helper.getNo() != startNo) {
            helper = helper.getNext();
        }
        //然后开始寻找要出列的前一个节点,先记录出列节点的编号,然后执行节点的出列,让nums-1,将helper指向新的要开始报数的节点
        //出列次数计数器
        int times = 1;
        while (nums !=0){
            //找到出列节点的前一个节点,用helper指向
            int no = helper.getNo();
            for (int i = no; i < no+countNo-2; i++) {
                helper = helper.getNext();
            }
            //记录节点编号
            System.out.println("第"+times+"次出列的编号为:"+helper.getNext().getNo());
            //出列次数加1
            times++;
            //执行出列操作,将要出列的前一个指向要出列的下一个即可,此时helper依然指向的是要出列的前一个,它的下一个为下一次开始报数的节点
            //TODO 当要删除的节点为first或last时,需要移动first和last的指向,否则还会存环形链表,以及移除最后一个的时候也需要切断他自己和自己的联系
            helper.setNext(helper.getNext().getNext());
            //出列了一个节点,链表总节点数减一
            nums--;
            //helper指向新的开始报数节点
            helper = helper.getNext();
        }
    }

}
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,544评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,430评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,764评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,193评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,216评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,182评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,063评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,917评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,329评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,543评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,722评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,425评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,019评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,671评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,825评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,729评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,614评论 2 353

推荐阅读更多精彩内容