[数据结构与算法]数据结构笔记 —— 单链表和双向链表

本篇博客是根据b站尚硅谷老师的数据结构教程，学习后写的学习笔记
部分概念和图片均来自视频，代码和截图均为自己动手，本篇博客的重点在自己编写的代码注释上
尚硅谷Java数据结构与java算法（Java数据结构与算法）

单链表

链表是有序的列表（Linked List），在内存中的存储方式如上图所示

（1）链表是以节点的方式来存储，是链式存储

（2）每个节点包含data域，next域。其中，data域用来保存当前节点要存储的数据，next域用来指向下一个节点

（3）链表的各个节点不一定是连续存储

（4）链表分为带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表（带头节点）逻辑结构示意图如下

这里看起来像是顺序连续存储，但实际上不是，下一个节点是什么，由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;
    }

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

创建单链表

class SingleLinkedList{
    //先初始化一个头节点，头节点不存放具体的数据，被初始化后就不要修改移动
    private HeroNode head = new HeroNode(0,"","");
}

一个完整的单链表应该可以实现节点的增删改查，所以
接下来就是往这个单链表类里面加上添加节点，删除节点，修改节点，遍历输出等方法

将新节点添加到单链表尾部

//方式一：添加节点到单向链表
    //思路，当不考虑编号顺序时，只需要找到当前链表的最后一个节点，然后让这个节点的next指向新的节点
    public void add(HeroNode heroNode){
        //通过一个辅助变量temp来遍历当前的链表，temp用来指向当前的节点
        HeroNode temp = head;
        //遍历链表找到最后一个节点
        while(true){
            if(temp.next == null){ //如果next为null，说明temp指向的当前节点是最后一个节点
                break;
            }
            //如果next不为空，则temp指向 next指向的节点对象，从而达到temp后移的效果
            temp = temp.next;
        }
        //通过break退出while循环的时候，temp就指向了链表的最后一个节点
        //让这个节点的next指向需要新加入链表的heroNode对象
        temp.next = heroNode;
    }

将新节点按照编号插入到指定位置

 //方式二：添加节点到单链表，根据编号no将节点插入到指定位置
    //而不是像方式一那样全部添加到单链表的最后
    public void addByNo(HeroNode heroNode){
        //同样借助temp来遍历整个单链表，temp初始等于head，说明从head开始遍历
        HeroNode temp = head;
        //如果要插入的位置已经有了相同编号no的节点，则不插入
        //flag为false说明没有重复节点，flag为true说明有重复编号no的节点
        boolean flag = false;
        /*
        temp一开始指向的是头节点，然后往后面遍历，heroNode是要插入的新节点
        拿heroNode的编号no 与 temp.next指向节点的编号no比较
        1. temp.next == null,说明已经来到链表最后，此时就像方式一将节点插入到链表末尾
        2. temp.next.no < heroNode.no,则temp继续往后面遍历
        3. temp.next.no == heroNode.no，将false置为true，说明有重复节点
        4. temp.next.no > heroNode.no，则当前temp.next的位置即为heroNode的正确位置
        第1和4中情况都说明找到插入位置，应该结束while循环，完成新节点的插入
         */
        while(true){
            if(temp.next == null){
                break;
            }
            if (temp.next.no > heroNode.no){
                break;
            }
            else if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next; //让temp后移遍历整个链表
        }
        if(flag){
            System.out.printf("准备插入的编号 %d 已经存在，插入失败\n",heroNode.no);
        } else {
            //将heroNode插入到temp的后面，即temp.next的位置
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

修改节点

//修改节点
    public void update(HeroNode newHeroNode){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
        }

        //根据no编号找到需要修改的节点
        //同样定义temp变量用来遍历链表
        HeroNode temp = head.next;
        //判断是否找到需要修改的节点，默认为false为找到，找到则为true
        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);
        }
    }

删除节点

//删除节点
    //temp指向需要删除节点的前一个节点
    //比较时，是temp.next.no 和 需要删除节点的no 比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag = false; //用来标志是否找到了待删除节点
        while(true){
            if(temp.next == null){
                //表示没有找到待删除节点，不修改flag，默认为false
                break;
            }
            if(temp.next.no == no){
                //只有这个情况才算是找到了待删除节点，把flag置为true
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }else{
            System.out.printf("需要删除的编号为 %d 的节点不存在\n",no);
        }
    }

显示全部节点

//显示链表
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
        }
        //同样通过辅助变量temp来遍历整个链表
        HeroNode temp = head.next;
        while(true){
            //判断链表是否到了最后
            if(temp==null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //temp后移，指向下一个节点
            temp = temp.next;
        }
    }

main函数

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(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        //将节点不按顺序的插入
        singleLinkedList.addByNo(hero1);
        singleLinkedList.addByNo(hero3);
        singleLinkedList.addByNo(hero4);
        singleLinkedList.addByNo(hero2);

        //创建一个新节点
        HeroNode newHeroNode = new HeroNode(2,"卢","玉");

        singleLinkedList.update(newHeroNode);

        singleLinkedList.del(4);

        //显示链表
        singleLinkedList.list();


    }

最终结果为

双向链表

双向链表与单向链表不同，单向链表每个节点只有一个next用来指向下一个节点，而双向链表每个节点有一个pre用来指向上一个节点，有一个next用来指向下一个节点。

图片来源：http://c.biancheng.net/view/3342.html

双向链表代码

创建节点

//定义HeroNode，每个HeroNode对象就是一个节点
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 + '\'' +
                '}';
    }
}

创建一个双向链表

//创建一个双向链表
class DoubleLinkedList{
    //创建一个头节点head
    HeroNode2 head = new HeroNode2(0,"","");
    //返回头节点
    public HeroNode2 getHead(){
        return head;
    }
}

将新节点插入到双向链表的最后面

public void add(HeroNode2 heroNode){
        //通过一个辅助变量temp来遍历当前的链表，temp用来指向当前的节点
        HeroNode2 temp = head;
        while(true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        //通过break退出while循环的时候，temp就指向了链表的最后一个节点
        //将新增节点加入到双向链表的最后面
        temp.next = heroNode;
        heroNode.pre = temp;
    }

按照编号将新节点插入到指定位置

//按照编号插入节点
    public void addByNo(HeroNode2 heroNode){
        HeroNode2 temp = head;
        boolean flag1 = false;
        boolean flag2 = false;
        while(true){
            if(temp.next == null){
                flag2 = true;
                break;
            }
            if(temp.next.no > heroNode.no){
                break;
            }
            if(temp.next.no == heroNode.no){
                flag1 = true;
                break;
            }
            temp = temp.next;
        }
        if(flag1){
            System.out.println("节点的no重复，插入失败");
        }else{
            if(!flag2){
                temp.next.pre = heroNode;
                heroNode.next = temp.next;
            }
            heroNode.pre = temp;
            temp.next = heroNode;
        }
    }

修改节点

//修改节点，与单链表里面的修改方法一样，只是改了节点类型
    public void update(HeroNode2 newHeroNode){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
        }
        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 del(int no){
        //判断当前链表是否为空
        if(head.next == null){
            System.out.println("当前链表为空，无法删除");
        }
        //不需要找前一个节点，因此temp可以从head.next节点开始遍历，而不是head节点
        HeroNode2 temp = head.next;
        boolean flag = false; //用来标志是否找到了待删除节点
        while(true){
            if(temp == null){
                //表示没有找到待删除节点，不修改flag，默认为false
                break;
            }
            if(temp.no == no){
                //只有这个情况才算是找到了待删除节点，把flag置为true
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            //找到待删除节点，可以直接删除
            temp.pre.next = temp.next;
            //如果temp正好是最后一个节点，那么上一句话等同于temp.pre.next = null
            //但是temp.next就是null，不能用null调用pre指针，因此需要加上一个判断
            //当temp是最后一个节点时，就不用执行下面这句话了
            if(temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else{
            System.out.printf("需要删除的编号为 %d 的节点不存在\n",no);
        }
    }

显示全部节点

//显示链表
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
        }
        //同样通过辅助变量temp来遍历整个链表
        HeroNode2 temp = head.next;
        while(true){
            //判断链表是否到了最后
            if(temp==null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //temp后移，指向下一个节点
            temp = temp.next;
        }
    }

main函数

 public static void main(String[] args) {
        //创建节点
        HeroNode2 hero1 = new HeroNode2(1,"宋江","及时雨");
        HeroNode2 hero2 = new HeroNode2(2,"卢俊义","玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3,"吴用","智多星");
        HeroNode2 hero4 = new HeroNode2(4,"林冲","豹子头");

        //创建一个双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addByNo(hero1);
        doubleLinkedList.addByNo(hero4);
        doubleLinkedList.addByNo(hero2);
        doubleLinkedList.addByNo(hero3);
        doubleLinkedList.list();
}

虽然插入顺序不同，但最终双向链表中节点是按照编号no的顺序从小到大排列的

加上修改和删除语句

//修改
HeroNode2 newHeroNode = new HeroNode2(4,"零充","没钱");
doubleLinkedList.update(newHeroNode);

//删除
doubleLinkedList.del(1);

doubleLinkedList.list();