重学数据结构单链表

Z时代
2024-01-10
分类：综合

链表种类繁多：单向链表，循环链表，双向链表等等。

链表是一种在内存中随意分布的，由内存地址通过指针相互链接而成的顺序结构。由于其特殊的内存分布特点，对于删除和添加的操作相对数组效率较高。在查找和修改效率较低

我们来学习一些单项链表的增删改查。

功能实现

对于链表可谓是又爱又恨，爱是因为它是真的好用，恨是因为晦涩难懂，来来回回学了几遍才搞懂。

定义单项链表节点类

链表中由两部分构成：数据 + 地址指针。头节点一般都是不存放数据，只是当做单项链表的开始索引，方便进行相关操作（头节点不一定都存在），地址指针存放着下一个节点的内存地址，最后一个节点的写一个指针地址为空。数据部分按需定义即可，这里数据部分有编号(no)和姓名(name)组成。

代码如下：

/**
 * 英雄节点类
 * @author laona
 */
class HeroNode {
    /**
     * 节点编号
     */
    int no;
    /**
     * 节点信息
     */
    String name;
    /**
     * 下一个节点
     */
    HeroNode next;
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    // 重写 toString 方法是为了方便遍历链表
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name="" + name + """ +
                "}";
    }
}

实现单向链表

定义个空的头节点，头节点只需要存放下一个节点的内存地址即可，空的链表头节点的 next == null

实现代码如下：

/**
 * 单链表类
 * @author huaian
 */
class SingleLinked {
    /**
     * 空的头节点，此时的 next == null
     */
    private HeroNode headNode = new HeroNode(0, "");
}

链表尾部添加节点

添加新的节点到链表，最重要的是找到链表的末尾节点(即链表的最后一个指向空的节点)，这就需要遍历链表。

遍历链表需要一个临时变量来获取链表当前不为空的节点 temp，直到最后一个为空的节点。

循环体条件为：

// 获取下一个节点 temp = temp.next

添加新节点语句为：

temp.next = newNode;

函数实现代码如下：

/**
 * 添加新的节点到单链表
 * @param newNode {@link HeroNode} 新的节点
 */
public void addNode(HeroNode newNode) {
    HeroNode temp = headNode;
    while (true) {
        if (temp.next == null) {
            break;
        }
        temp = temp.next;
    }
    temp.next = newNode;
}

以上添加功能就完成了，那么能否让链表中的数据按照 no 的顺序来排列呢？肯定是可以的。

按照升序添加节点

按照升序排序其实也不难，实现代码和链表尾部添加节点的代码差不多。需要弄明白的一个核心是：链表只能通过前一个节点的 next 去获取下一个节点，那么就需要传入的 no 和前一个节点的 next.no 比较。

比较条件：

temp.next.no >= newNode.no

函数代码如下：

/**
 * 按编号升序添加节点
 * @param newNode {@link HeroNode} 新的节点
 */
public void addNodeByOrder(HeroNode newNode){
    HeroNode temp = headNode;
    while (true) {
        if (temp.next == null) {
            break;
        }
        if (temp.next.no >= newNode.no) {
            // 不能有相同的节点
            if (temp.next.no == newNode.no) {
                System.out.printf("已存在索引相同的元素: no = %d，插入失败
", newNode.no);
                break;
            }
            newNode.next = temp.next;
            temp.next = newNode;
            break;
        } else {
            temp = temp.next;
        }
    }
    temp.next = newNode;
}

修改节点信息

修改节点信息就是比较当前节点的下一个节点信息和需要修改的节点信息是否相同，如果相容那么就直接修改，不相同就继续比较下一个节点。

函数实现代码如下：

/**
 * 根据节点编号修改信息
 * @param no 节点编号
 * @param newName 节点信息
 */
public void modifyByNo(int no, String newName) {
    HeroNode temp = headNode;
    while (true) {
        if (temp.next == null) {
            System.out.printf("不存在，编号为：%d 的节点
", no);
            break;
        }
        if (temp.next.no == no) {
            temp.next.name = newName;
            break;
        }
        temp = temp.next;
    }
}

删除节点

有了前面的铺垫，删除节点就很简单了。删除节点需要明确是删除哪一个节点，这里就通过 no 删除节点，这里也需要通过比较当前节点的下一个节点信息和待删除的节点信息是否相同，相同则删除。

删除代码（通过把当前的节点的 next 指向当前节点的 next.next）：

// 通过把当前的节点的 next 指向当前节点的 next.next temp.next = temp.next.next;

函数代码如下：

/**
 * 通过 no 删除节点
 * @param no 节点编号
 */
public void dropNodeByINo(int no) {
    HeroNode temp = headNode;
    while (true) {
        if (temp.next == null) {
            System.out.printf("不存在，编号为：%d 的节点
", no);
            break;
        }
        if (temp.next.no == no) {
            temp.next = temp.next.next;
            break;
        }
        temp = temp.next;
    }
}

遍历链表

方便查看链表的内容，编写一个函数遍历链表，代码如下：

/**
 * 遍历单链表的所有节点
 */
public void list() {
    HeroNode temp = headNode;
    if (headNode.next == null) {
        System.out.println("该链表为空~！");
        return;
    }
    while (true) {
        if (temp.next == null) {
            break;
        }
        System.out.println(temp.next);
        temp = temp.next;
    }
}

单链表类的整体

为了方便查看这里还是把 SingleLinked 的代码整体代码贴一下（节省篇幅，函数只添加头部，函数体省略）

SingleLinked 类的代码如下：

/**
 * 单链表类
 * @author huaian
 */
class SingleLinked {
    private HeroNode headNode = new HeroNode(0, "");
    /**
     * 通过 no 删除节点
     * @param no 节点编号
     */
    public void dropNodeByINo(int no) {
       ······
    }
    /**
     * 根据节点编号修改信息
     * @param no 节点编号
     * @param newName 节点信息
     */
    public void modifyByNo(int no, String newName) {
        ······
    }
    /**
     * 按编号升序添加节点
     * @param newNode {@link HeroNode} 新的节点
     */
    public void addNodeByOrder(HeroNode newNode){
        ······
    }
    /**
     * 添加新的节点到单链表
     * @param newNode {@link HeroNode} 新的节点
     */
    public void addNode(HeroNode newNode) {
        ······
    }
    /**
     * 遍历单链表的所有节点
     */
    public void list() {
        ······
    }
}
/**
 * 英雄节点类
 * @author huaian
 */
class HeroNode {
    /**
     * 节点编号
     */
    int no;
    /**
     * 节点信息
     */
    String name;
    /**
     * 下一个节点
     */
    HeroNode next;
    // 构造传参
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name="" + name + """ +
                "}";
    }
}