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

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

双向链表

之前在 学会用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