生如风
github icon

数据结构与算法—链表之单链表

author icon生如风calendar icon2023年1月4日category icon
tag icon
timer icon大约 8 分钟

[TOC]

2023年的第一篇文章

在开发过程中，选择合适的数据结构是很重要的，可以快速处理数据的存储及使用问题。计划有时间慢慢系统的学习《数据结构与算法》，看看视频，练习实践，最后用于工作中。

链表

单链表

结构和特点

链表是有序的列表，在内存中的存储结构如下：

特点：

  • 以节点的方式存储，是链式存储
  • 每个节点包含data域（用于存放数据），next域（指向下一个节点）
  • 链表的各个节点在内存中不一定是连续存储的
  • 链表分为带head节点和不带head节点的

链表的逻辑结构：

创建添加

因为链表是以节点存储，在创建链表时，就根据节点一个个添加连接起来。需要先创建一个head节点，根据head节点指向下一个节点，一个个串起来。

1、创建节点类

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 + '\'' +
                '}';
    }
}

2、有了节点类后，就可以创建head头结点，然后根据head节点，进行节点添加。

有两种添加方法，一种是顺序添加，另一种是根据英雄编号大小排序添加。

顺序添加：

// 创建一个单链表类，并添加操作
class SingleLickedList {
    // 创建头结点
    private HeroNode head = new HeroNode(0, "", "");

    // 添加节点到单链表
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，需要一个辅助指针进行遍历 temp
        HeroNode temp = head;
        // 遍历链表，找到最后一个节点，添加新节点
        while (true) {
            // 找到最后一个节点，因为最后的节点的next域为NULL
            if (temp.next == null) {
                break;
            }
            // 没有找到，temp后移
            temp = temp.next;
        }

        // 当退出while 循环时，temp 就指向了最后一个节点
        temp.next = heroNode;
    }
}

有了添加操作，为了方便测试，需要能够遍历链表，打印出里面的数据。

在SingleLickedList 类中添加方法list

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.next;
    }
}

测试：

public static void main(String[] args) {
    // 创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(3, "李逵", "黑旋风");
    HeroNode hero3 = new HeroNode(2, "林冲", "豹子头");

    SingleLickedList list = new SingleLickedList();
    list.add(hero1);
    list.add(hero2);
    list.add(hero3);
    list.list();
}

结果：

可以看到正常添加完节点，并且按照添加的顺序显示。

有序添加：

就是在添加节点之前，查询是否有相同节点存在，如果存在，就不添加；查询下一个节点的编号no 是否大于需要添加节点的编号no，大于就表示要添加的节点就在下一个节点之前。

也就是根据节点的no ，有序的添加，创建方法 add2：

// 创建一个单链表类，并添加操作
class SingleLickedList {
    // 头结点
    private HeroNode head = new HeroNode(0, "", "");

    public void add2(HeroNode heroNode) {
        HeroNode temp = head;
        // 表示该节点是否找到相同编号的节点存在，false：未找到，true：找到
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 找到了位置，应该放在temp之后
                break;
            } else if (temp.next.no == heroNode.no) {
                // 已经有相同节点
                flag = true;
                break;
            }
            // 指针后移
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("待加入的英雄编号：%d已经有了", heroNode.no);
        } else {
            // 加入
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 添加节点到单链表
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，需要一个辅助指针进行遍历 temp
        HeroNode temp = head;
        // 遍历链表，找到最后一个节点，添加新节点
        while (true) {
            // 找到最后一个节点，因为最后的节点的next域为NULL
            if (temp.next == null) {
                break;
            }
            // 没有找到，temp后移
            temp = temp.next;
        }

        // 当退出while 循环时，temp 就指向了最后一个节点
        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.next;
        }
    }
}

测试：

public static void main(String[] args) {
    // 创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(3, "李逵", "黑旋风");
    HeroNode hero3 = new HeroNode(2, "林冲", "豹子头");

    SingleLickedList list = new SingleLickedList();
    list.add(hero1);
    list.add(hero2);
    list.add(hero3);
    list.list();

    System.out.println("-------------------------");
    SingleLickedList list2 = new SingleLickedList();
    list2.add2(hero1);
    list2.add2(hero2);
    list2.add2(hero3);
    list2.list();
}

可以看到add2 所执行的是按顺序的

修改

根据节点数据的编号no，修该英雄的昵称nickname，创建方法 update

// 创建一个单链表类，并添加操作
class SingleLickedList {
    // 头结点
    private HeroNode head = new HeroNode(0, "", "");

    // 更新节点
    public void update(HeroNode heroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false; //是否找到需要修改的节点
        while (true) {
            if (temp.next == null) {
                break; //已经遍历完链表
            }
            if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next.nickName = heroNode.nickName;
        } else {
            System.out.println("没有相关节点");
        }
    }

    public void add2(HeroNode heroNode) {
        HeroNode temp = head;
        // 表示该节点是否找到相同编号的节点存在，false：未找到，true：找到
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 找到了位置，应该放在temp之后
                break;
            } else if (temp.next.no == heroNode.no) {
                // 已经有相同节点
                flag = true;
                break;
            }
            // 指针后移
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("待加入的英雄编号：%d已经有了", heroNode.no);
        } else {
            // 加入
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 添加节点到单链表
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，需要一个辅助指针进行遍历 temp
        HeroNode temp = head;
        // 遍历链表，找到最后一个节点，添加新节点
        while (true) {
            // 找到最后一个节点，因为最后的节点的next域为NULL
            if (temp.next == null) {
                break;
            }
            // 没有找到，temp后移
            temp = temp.next;
        }

        // 当退出while 循环时，temp 就指向了最后一个节点
        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.next;
        }
    }
}

测试：

public static void main(String[] args) {
        // 创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(3, "李逵", "黑旋风");
        HeroNode hero3 = new HeroNode(2, "林冲", "豹子头");

        SingleLickedList list2 = new SingleLickedList();
        list2.add2(hero1);
        list2.add2(hero2);
        list2.add2(hero3);
        list2.list();

        // 测试更新节点
        System.out.println("------------------------");
        // 无相关节点
        list2.update(new HeroNode(4, "宋江", "梁上好汉"));
        list2.list();

        System.out.println("------------------------");
        // 修改成功
        list2.update(new HeroNode(1, "宋江", "梁上好汉"));
        list2.list();
}

删除

// 创建一个单链表类，并添加操作
class SingleLickedList {
    // 头结点
    private HeroNode head = new HeroNode(0, "", "");

    // 删除节点    这里可以根据需求将参数HeroNode 设置为只传入编号no即可
    public void delete(HeroNode heroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                 break;     // 已遍历完链表
            }

            if (temp.next.no == heroNode.no) {
                // 找到要删除的节点
                flag = true;
                break;
            }

            temp = temp.next;       // 指针后移
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有相关节点");
        }

    }

    // 更新节点
    public void update(HeroNode heroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false; //是否找到需要修改的节点
        while (true) {
            if (temp.next == null) {
                break; //已经遍历完链表
            }
            if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next.nickName = heroNode.nickName;
        } else {
            System.out.println("没有相关节点");
        }
    }

    public void add2(HeroNode heroNode) {
        HeroNode temp = head;
        // 表示该节点是否找到相同编号的节点存在，false：未找到，true：找到
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 找到了位置，应该放在temp之后
                break;
            } else if (temp.next.no == heroNode.no) {
                // 已经有相同节点
                flag = true;
                break;
            }
            // 指针后移
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("待加入的英雄编号：%d已经有了", heroNode.no);
        } else {
            // 加入
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 添加节点到单链表
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，需要一个辅助指针进行遍历 temp
        HeroNode temp = head;
        // 遍历链表，找到最后一个节点，添加新节点
        while (true) {
            // 找到最后一个节点，因为最后的节点的next域为NULL
            if (temp.next == null) {
                break;
            }
            // 没有找到，temp后移
            temp = temp.next;
        }

        // 当退出while 循环时，temp 就指向了最后一个节点
        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.next;
        }
    }
}

测试：

public static void main(String[] args) {
        // 创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(3, "李逵", "黑旋风");
        HeroNode hero3 = new HeroNode(2, "林冲", "豹子头");

        // 测试删除
        SingleLickedList list = new SingleLickedList();
        list.add(hero1);
        list.add(hero2);
        list.add(hero3);
        System.out.println("删除数据前的链表~~~~~~");
        list.list();

        System.out.println("删除数据后的链表~~~~~~");
        list.delete(new HeroNode(3, "李逵", "黑旋风"));
        list.list();

        System.out.println("删除数据后的链表~~~~~~");
        list.delete(new HeroNode(1, "宋江", "及时雨"));
        list.delete(new HeroNode(2, "林冲", "豹子头"));
        list.list();
    }

删除完数据后，链表就为空

到这，暂时学习了单链表的增删改查。

可以看看我的个人博客： 网站：https://www.fuzm.wangopen in new window / https://liwangc.gitee.ioopen in new window ————————————————————————— 作为初学者，很多知识都没有掌握，见谅，如有错误请指出，以期进步，感谢！。后续有新的学习，继续补充上来。

默认页脚
Copyright © 2026 生如风