Java 实现单链表

单链表是一种常用的数据结构，它由若干个节点（Node）组成，每个节点包含两部分：一部分是数据域，用于存储数据；另一部分是指针域，用于指向下一个节点。。

节点类

定义的节点类：

public class HeroNode {

    public int no;

    public String name;

    public HeroNode next; //指向下一个节点

    public HeroNode(int no, String name, HeroNode next) {
        this.no = no;
        this.name = name;
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}

在这个代码中，HeroNode 类定义了三个实例变量：no 表示英雄编号，name 表示英雄姓名，next 表示指向下一个节点的引用。

构造方法用于初始化对象的属性，toString() 方法用于打印节点的信息。

定义单链表类

public class SingleLinkedList {

    /** 初始化头节点 不存放数据 只是一个标记 */
    private HeroNode head = new HeroNode(0, "", null);


    /** 插入节点 尾插法 */
    public void add(HeroNode newNode){
        if( newNode == null ){
            return;
        }
        HeroNode currentNode = head;
        while ( currentNode.next != null ) {
            currentNode = currentNode.next;
        }
        currentNode.next = newNode;
    }

    /** 修改节点 */
    public void update(HeroNode newNode){
        if( newNode == null ){
            return;
        }
        HeroNode currentNode = head.next;
        while ( currentNode != null ){
            if( currentNode.no == newNode.no ){
                currentNode.name = newNode.name;
            }
            currentNode = currentNode.next;
        }
    }

    /** 删除节点 */
    public void delNode(int no){
        HeroNode currentNode = head;
        while ( currentNode != null && currentNode.next != null ) {
            if( currentNode.next.no == no ){
                currentNode.next = currentNode.next.next;
            }
            currentNode = currentNode.next;
        }
    }

    /** 展示列表 */
    public void show(){
        HeroNode currentNode = head.next;
        while ( currentNode != null ) {
            System.out.println(currentNode);
            currentNode = currentNode.next;
        }
    }

}

在 SingleLinkedList 类中实现了以下几个方法：

add(HeroNode newNode)：在链表的尾部插入一个新节点。

update(HeroNode newNode)：根据节点编号找到指定节点，并更新节点的姓名。

delNode(int no)：根据节点编号找到指定节点的前一个节点，并将其 next 引用指向下一个节点，从而实现删除节点的功能。

show()：遍历链表，并打印每个节点的信息。

这些方法都是单链表常见的操作，有几个小地方需要注意：

在 add(HeroNode newNode) 方法中，使用的是尾插法，即将新节点添加到链表的尾部。这是常用的插入方法之一，可以有效地保持链表的顺序性。

在 update(HeroNode newNode) 方法中，首先需要找到待修改的节点，然后更新其数据。这是正确的操作。但是，在找到节点后，没有中断循环，而是继续遍历链表直到结束，是因为考虑到链表中可以存在重复的节点。

在 delNode(int no) 方法中，首先需要找到待删除节点的前一个节点，然后将其 next 引用指向待删除节点的下一个节点。

在 show() 方法中，你首先将头节点赋给 currentNode，然后通过 currentNode.next 遍历链表。这样做是为了跳过头节点，只展示真实数据节点。这也是常见的展示列表的操作。

以上就是一个单链表的简单的实现。

总结

单链表的特点包括：

• 链表中的节点是通过指针相连的，每个节点都指向下一个节点，最后一个节点指向空（null）。
• 单链表可以动态地增加、删除节点，而不需要移动其他节点的位置。
• 链表的插入和删除操作效率高，时间复杂度为 O(1)。
• 链表的查找操作相对较慢，时间复杂度为 O(n)，需要从头节点开始依次向后遍历。

单链表的优势在于可以方便地进行插入和删除操作，但其缺点是查找操作效率较低。在实际编程中，单链表常用于不需要频繁查找操作，但需要频繁插入和删除操作的场景中。

单链表是一种重要的数据结构，能够有效地解决一些特定的问题，例如处理动态数据或者构建一些数据结构。