数据结构 [Java版本] 链表之双链表和单向环形链表

双向链表应用实例

使用带head头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点.
示意图帮助理解删除

双向链表的第二种添加方式,按照编号顺序 [示意图]
按照单链表的顺序添加，稍作修改即可.


示意图
分析 双向链表的遍历，添加，修改，删除的操作思路 ==>> 代码实现
  1. 遍历 方和 单链表一样，只是可以向前，也可以向后查找
  2. 添加 (默认添加到双向链表的最后)
    (1) 先找到双向链表的最后这个节点
    (2) temp.next = newHeroNode
    (3) newHeroNode.pre = temp;
  3. 修改 思路和 原来的单向链表一样.
  4. 删除
    (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
    (2) 直接找到要删除的这个节点，比如temp
    (3) temp.pre.next = temp.next
    (4) temp.next.pre = temp.pre;

代码实现

package cn.icanci.datastructure.linkedlist;

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.datastructure.linkedlist
 * @Date: Created in 2020/3/1 20:08
 * @ClassAction: 双向链表
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向链表的测试");
        //先创建节点
        HeroNode2 hero1 = new HeroNode2(1, "德玛西亚", "大保健");
        HeroNode2 hero5 = new HeroNode2(5, "QQ", "qq");
        HeroNode2 hero2 = new HeroNode2(2, "德玛西亚皇子", "皇子");
        HeroNode2 hero3 = new HeroNode2(3, "无极剑圣", "剑圣");
        HeroNode2 hero4 = new HeroNode2(4, "蒸汽机器人", "机器人");
        //创建双向链表对象
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        doubleLinkedList.add(hero5);
        //打印
        doubleLinkedList.list();
        System.out.println("========================================");
        //修改
        HeroNode2 newHeroNode = new HeroNode2(4, "安其拉", "啊");
        doubleLinkedList.update(newHeroNode);
        doubleLinkedList.list();
        System.out.println("========================================");
        //删除
        doubleLinkedList.delete(2);
        doubleLinkedList.list();
    }
}

//创建一个双向链表的类
class DoubleLinkedList{
    //初始化 一个头节点
    private HeroNode2 head = new HeroNode2(0,"","");

    //返回头节点
    public HeroNode2 getHead(){
        return head;
    }

    //遍历双向链表
    public void list(){
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动 因此需要一个辅助变量
        HeroNode2 temp = head.next;
        while (true) {
            //判断链表是否到最后
            if (temp == null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将 temp 后移
            temp = temp.next;
        }
    }
    public void add(HeroNode2 heroNode) {
        //因为head节点不能动,因此我们需要一个辅助遍历 temp
        HeroNode2 temp = head;
        //遍历链表,找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后,将temp后移
            temp = temp.next;
        }
        //当退出while循环的时候,temp就指向链表的最后
        //将最后这个节点的next指向新的节点
        //添加到最后一个节点
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改双向链表的数据
    public void update(HeroNode2 heroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点,根据no编号
        //定义一个辅助变量
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                //已经遍历完毕
                break;
            }
            if (temp.no == heroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.println("没有找到编号为:" + heroNode.no + " 的信息");
        }

    }

    //删除一个节点
    //对于双向链表 可以直接找到此节点
    public void delete(int no) {
        //判断当前链表是否空
        if (head.next == null){
            System.out.println("链表为空,无法删除");
            return ;
        }
        HeroNode2 temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                //已经打到结点的最后
                break;
            }
            if (temp.next.no == no) {
                //找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断 flag
        if (flag) {
            //找到
           temp.pre.next = temp.next;
           //如果是最后一个节点 下面的这句话就不用执行了
           if (temp.next!=null){
               temp.next.pre = temp.pre;
           }
        } else {
            System.out.println("需要删除的节点:" + no + " 不存在");
        }
    }


}


class HeroNode2 {
    public int no;
    public String name;
    public String nickName;
    //指向下一个节点
    public HeroNode2 next;
    //指向前一个节点
    public HeroNode2 pre;

    //构造器
    public HeroNode2(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

按照序号添加

 public void addByOrder(HeroNode2 heroNode) {
        //因为头节点不能动 所以需要一个辅助指针
        //因为是单链表 因此需要找的temp.是位于添加位置前面的一个节点 否则插入不了
        HeroNode2 temp = head;
        //flag标识添加的编号是否存在 默认为  false
        boolean flag = false;
        while (true) {
            //说明已经再链表最后了
            if (temp.next == null) {
                break;
            }
            //位置找到再 temp 的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //说明编号已经存在
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        //判断 flag 的值
        if (flag == true) {
            //不能添加 说明编号存在
            System.out.println("准备插入的编号:" + heroNode.no + "已经被占用");
        } else {
            //插入到链表中
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    }
单向环形链表

单向环形链表应用场景


丢手帕问题

Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。


单项环链表

约瑟夫问题的示意图

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下


示意图

约瑟夫问题的代码实现

构建一个单向的环形链表思路

  1. 先创建第一个节点, 让 first 指向该节点，并形成环形
  2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

遍历环形链表

  1. 先让一个辅助指针(变量) curBoy，指向first节点
  2. 然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束

代码实现

package cn.icanci.datastructure.linkedlist;

import javax.xml.transform.Source;

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.datastructure.linkedlist
 * @Date: Created in 2020/3/1 21:27
 * @ClassAction:  Josephu 问题
 */
public class JosephuLinkedList {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
    }
}

//创建一个环形的单项链表
class CircleSingleLinkedList{
    //创建一个first节点
    private Boy first = new Boy(-1);

    //添加小孩子节点
    public void addBoy(int nums){
        //nums 进行数据校验
        if (nums<-1){
            System.out.println("输入的数据不正确");
        }

        //辅助指针
        Boy curBoy = null;
        //使用for循环创建环形链表
        for (int i = 1; i <= nums ; i++) {
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //如果式第一个小孩
            if (i == 1){
                first = boy;
                //构成环
                first.setNext(boy);
                //让 curBoy 指向第一个小孩
                curBoy = first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历所有的数据
    public void showBoy(){
        //判断链表是否为空
        if (first == null){
            System.out.println("链表为空");
            return ;
        }
        //因为first不能动 所以需要一个辅助值
        Boy curBoy = first;
        while (true){
            System.out.println("当前的小孩子编号为:"+curBoy.getNo());
            if (curBoy.getNext() == first){
                break;
            }
            //后移
            curBoy = curBoy.getNext();
        }
    }
}

//创建一个Boy 表示一个节点
class Boy{
    private int no;
    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;
    }
}
约瑟夫出队列的分析

根据用户的输入，生成一个小孩出圈的顺序
n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下

  1. 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.
    补充： 小孩报数前，先让 first 和 helper 移动 k - 1次
  2. 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次
  3. 这时就可以将first 指向的小孩节点 出圈
    first = first .next
    helper.next = first
    原来first 指向的节点就没有任何引用，就会被回收

出圈的顺序
2->4->1->5->3

约瑟夫问题出队列分析

代码实现

package cn.icanci.datastructure.linkedlist;

import com.sun.org.apache.xpath.internal.SourceTree;

import javax.xml.transform.Source;
import java.nio.file.FileStore;

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.datastructure.linkedlist
 * @Date: Created in 2020/3/1 21:27
 * @ClassAction: Josephu 问题
 */
public class JosephuLinkedList {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
        System.out.println("=========================================");
        circleSingleLinkedList.countBoy(2,3,5);
    }
}

//创建一个环形的单项链表
class CircleSingleLinkedList {
    //创建一个first节点
    private Boy first = new Boy(-1);

    //添加小孩子节点
    public void addBoy(int nums) {
        //nums 进行数据校验
        if (nums < -1) {
            System.out.println("输入的数据不正确");
        }

        //辅助指针
        Boy curBoy = null;
        //使用for循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            //如果式第一个小孩
            if (i == 1) {
                first = boy;
                //构成环
                first.setNext(boy);
                //让 curBoy 指向第一个小孩
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历所有的数据
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        //因为first不能动 所以需要一个辅助值
        Boy curBoy = first;
        while (true) {
            System.out.println("当前的小孩子编号为:" + curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            //后移
            curBoy = curBoy.getNext();
        }
    }

    //根据用户的输入 计算输出的顺序

    /**
     * @param startNo  表示从第几个小孩开始数
     * @param countNum 表示数几下
     * @param nums     表示最初由多少小孩在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有问题");
        }
        //创建需要给辅助指针.事先指向环形链表的最后一个节点
        Boy helper = first;
        while (true) {
            if (helper.getNext() == first) {
                //说明helper指向了最后一个节点
                break;
            }
            helper = helper.getNext();
        }
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数的时候 让 first 和 helper 指针同时移动 m - 1 次 然后出圈
        //这是一个循环操作 直到圈中只有一个节点
        while (true) {
            if (helper == first) {
                //圈中只有一个
                break;
            }
            //让first和helper指针同时移动countNum - 1
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时候first指向的节点就是要出圈的节点
            System.out.println(first.getNo() + "号小孩出圈");
            //这个时候需要使得小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后在圈中的小孩编号:" + first.getNo());
    }
}

//创建一个Boy 表示一个节点
class Boy {
    private int no;
    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;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,294评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,780评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,001评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,593评论 1赞 289
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,687评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,679评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,667评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,426评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,872评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,180评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,346评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,019评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,658评论 3赞 323
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,268评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,495评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,275评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,207评论 2赞 352