数据结构笔记 —— 单链表和双向链表

本篇博客是根据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();

数据结构笔记 —— 单链表和双向链表

上一篇:Java数据结构 | 单链表的代码实现


下一篇:单链表-数据结构