数据结构单链表详解

08-03 10:01 3563浏览

举报 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字

数据结构单链表详解

单链表的创建,显示

按照顺序添加

单链表修改节点：

相关课程更多>

作者相关文章更多>

推荐相关文章更多>

发评论

举报

数据结构单链表详解

单链表的创建,显示

按照顺序添加

单链表修改节点：

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

发评论

举报

相关课程更多>