DoubleLinkList

双链表
数据结构——学习双链表

单项链表与双向链表对比

单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找

单项链表不能自我删除，需要靠辅助节点，找到一个temp，temp是待删除节点的前一个节点。双向链表，则可以自我删除。

点我预览

这里有张图片：

相对于单项链表,双向链表增加了pre,来指向前一个节点,从而达到双向

---

增删改查分析

分析 :双向链表的遍历,增加,删除,修改的操作思路

• 遍历 :和单链表一样,不光可以向前查找,也可以向后

• 添加 :(默认添加到链表最后)

  • 先找到双向链表的最后节点

  • temp.next=newHeroNode

  • newHeroNode.pre=temp

• 修改 :的思路和原理与单链表一样(通过遍历找到节点的.no然后改data值)
• 删除
  • 因为是双向链表,因此可以自我删除,不需要找前后值
  • 直接找到要删除的节点,比如temp
  • temp.pre.next=temp.next(例如删除5号节点,把2号的next指向9号)
    点我预览

    这里有张图片：
    

先定义HeroNode

//定义一个heroNode,每个HeroNode 对象是一个节点
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;  //指向后一个节点  默认为null
    public HeroNode2 pre;  //指向前一个节点   默认为null

    //构造器
    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 + "]";
    }
}

增删改查代码实现

//创建一个双向链表的类
class DoubleLinkList {
    //先初始化一个头节点,头节点不要动，不存放具体数据
    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;
        }

    }

    //添加只能添加到最后
    //思路，当不考虑编号顺序时，
//        1.找到链表最后一个节点
//        2.将最后这个节点的next指向新节点
    public void add ( HeroNode2 heroNode ) {
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表找到最后
        while (true) {
            //找到链表的最后
            if ( temp.next == null ) {
                break;
            }
            temp = temp.next;
        }
        //当退出while时，temp就指向最后
        //形成一个双向链表
        temp.next    = heroNode;
        heroNode.pre = temp;
    }

    //添加，按照编号顺序添加（与单链表差不多，只是要多考虑pre）
    //如果有这个排名提示添加失败
    public void addpro ( HeroNode2 heroNode ) {
        //因为头节点不能动，因此仍需要辅助节点来帮助我们添加
//        因为单链表,因此我们找的temp是位于添加位置的前一个节点，否则添加不进去
        HeroNode2 temp = head;
        boolean flag = false; //标志添加的编号是否存在，默认为false
        boolean flag2 = false;
        while (true) {
            if ( temp.next == null ) {//说明temp已经在链表最后
                flag2=true;
                break;
            }
            if ( temp.next.no > heroNode.no ) {//位置找到，就在temp后面插入
                break;
            }
            else if ( temp.next.no == heroNode.no ) {//要添加的heronode存在
                flag = true;
                break;
            }
            temp = temp.next;//后移遍历
        }
        if ( flag ) {//编号存在
            System.out.printf ( "准备插入的英雄编号%d,已经存在,不能加入\n", heroNode.no );
        }
        else if (  flag2 ) {
            heroNode.pre=temp;
            temp.next = heroNode;
        }
        else{
            //插入到正确位置。temp后面
            HeroNode2 next = temp.next;
            heroNode.next = temp.next;
            temp.next = heroNode;
            next.pre=heroNode;
            heroNode.pre = temp;
        }

    }

    //修改一个节点的内容
    //修改节点的信息，根据no来修改，name，nickname
    public void updata ( HeroNode2 newHeroNode ) {
        //判断是否为空
        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 == newHeroNode.no ) {
                //找到节点
                flag = true;
                break;
            }
            temp = temp.next;

        }
        //根据flag判断节点是否可以找到
        if ( flag ) {
            temp.name     = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }
        else {//没有找到
            System.out.printf ( "没有找到编号%d的节点，无法修改\n", newHeroNode.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.next == null ) {  //到最后
                break;
            }
            if ( temp.no == no ) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if ( flag ) {
            temp.pre.next = temp.next;
            if ( temp.next != null ) {
                temp.next.pre = temp.pre;  //有条件，不能是最后一个，否则会出现空指针异常
            }
        }
        else {
            System.out.printf ( "列表中的no值无%d,无法删除\n", no );
        }
    }

    //查找
    public void find ( int no ) {
        HeroNode2 temp = head;
        boolean flag = false;
        while (true) {
            if ( temp.next == null ) {
                break;
            }
            if ( temp.no == no ) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if ( flag ) {
            System.out.println ( "你查找的信息如下：" );
            System.out.println ( temp );
        }
        else {
            System.out.printf ( "列表中的no值无%d,无法查到\n", no );
        }
    }
}

测试

public class DoubleLinkListDemo {
    public static void main ( String[] args ) {
        //测试
        System.out.println ( "双向链表的一个测试" );
        HeroNode2 hero1 = new HeroNode2 ( 1, "松江", "及时雨" );
        HeroNode2 hero2 = new HeroNode2 ( 2, "卢俊义", "玉麒麟" );
        HeroNode2 hero3 = new HeroNode2 ( 3, "吴用", "智多星" );
        HeroNode2 hero4 = new HeroNode2 ( 4, "林冲", "豹子头" );

        //创建一个双向链表
        DoubleLinkList doubleLinkList = new DoubleLinkList ( );
        /*//按照添加的顺序来添加
        doubleLinkList.add ( hero1 );
        doubleLinkList.add ( hero2 );
        doubleLinkList.add ( hero3 );
        doubleLinkList.add ( hero4 );
        //打印出来
        doubleLinkList.list ();*/

        //按照no值来添加
        doubleLinkList.addpro ( hero1 );
        doubleLinkList.addpro ( hero3 );
        doubleLinkList.addpro ( hero2 );
        doubleLinkList.addpro ( hero4 );
        doubleLinkList.list ();


        //修改
        HeroNode2 newHeroNode2 = new HeroNode2 ( 4, "公孙胜", "入云龙" );
        doubleLinkList.updata ( newHeroNode2 );
        System.out.println ("修改后" );
        doubleLinkList.list ();

        //删除
        doubleLinkList.delete ( 3 );
        System.out.println ("删除后的链表情况" );
        doubleLinkList.list ( );

        //查找
        doubleLinkList.find ( 3 );


    }
}