动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

数据结构单链表详解

08-03 10:01 356浏览
举报 T字号
  • 大字
  • 中字
  • 小字

1.链表是以节点的方式来存储的

2.每个节点包含data域,next域,next域指向下一节点

3.链表的各个节点不一定是连续存储的(内存中不一定是连续存储的,但是我们为了学习,通常树上画出来的是有顺序的)

4.链表分为带头节点的链表和不带头节点的链表,头节点不存放数据,它只用来表示单链表的头

单链表的创建,显示

创建 :

1.先创建头节点,作用是表示单链表的头

2.后面每添加一个节点,就直接加入到链表的最后,需要用一个 辅助指针

遍历:通过一个辅助指针,帮助遍历整个单链表

下面是一个添加梁山好汉的例子:

package Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
        test.addHeroNode(heroNode);
        test.addHeroNode(heroNode1);
        test.addHeroNode(heroNode2);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空,就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时,temp指向链表的最后,然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探,如果指针指向的下一个节点不为空,指针后移,如果为空,则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

但是上述添加没有添加到指定的位置

按照顺序添加

1.首先找到新添加的节点的位置(应该放在什么地方的位置,通过辅助指针)

2.新的节点.next = temp.next

3.将temp.next = 新的节点

package Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
        test.addByOrder(heroNode);
        test.addByOrder(heroNode2);
        test.addByOrder(heroNode1);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空,就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时,temp指向链表的最后,然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //按顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//标志编号是否存在
        while (true){
            if (temp.next== null){
                break;
            }
            if (temp.next.no > heroNode.no){//找到位置
                break;
            }
            else if (temp.next.no == heroNode.no){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("插入的编号已经存在");
        }
        else {
            //插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探,如果指针指向的下一个节点不为空,指针后移,如果为空,则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

单链表修改节点:

package Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
//        test.addHeroNode(heroNode);
//        test.addHeroNode(heroNode2);
//        test.addHeroNode(heroNode1);
        test.addByOrder(heroNode);
        test.addByOrder(heroNode2);
        test.addByOrder(heroNode1);
        test.list();
        //测试修改
        HeroNode newHeroNode = new HeroNode(2,"卢俊义","小义");
        test.update(newHeroNode);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空,就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时,temp指向链表的最后,然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //按顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//标志编号是否存在
        while (true){
            if (temp.next== null){
                break;
            }
            if (temp.next.no > heroNode.no){//找到位置
                break;
            }
            else if (temp.next.no == heroNode.no){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("插入的编号已经存在");
        }
        else {
            //插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改节点信息,根据和编号no,no不能修改
    public void update(HeroNode newHeroNode){
        //判空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //辅助指针
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;//遍历完了
            }
            if (temp.no == newHeroNode.no){
                flag = true;//找到
                break;
            }
            //继续遍历
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }
        else {
            //没找到
            System.out.println("没有找到修改的编号");
        }
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探,如果指针指向的下一个节点不为空,指针后移,如果为空,则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

还要会单链表反转,获取倒数第k个节点,逆序打印单链表等

动力节点在线课程涵盖零基础入门,高级进阶,在职提升三大主力内容,覆盖Java从入门到就业提升的全体系学习内容。全部Java视频教程免费观看,相关学习资料免费下载!对于火爆技术,每周一定时更新!如果想了解更多相关技术,可以到动力节点在线免费观看数据结构视频教程哦!

0人推荐
共同学习,写下你的评论
0条评论
杨晶珍
程序员杨晶珍

98篇文章贡献357785字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消