java实现简单单链表

Java实现简单单链表的完整攻略

什么是单链表

单链表是一种常见的数据结构，基于节点和指针实现，通过指针将多个节点连接在一起，每个节点包含当前节点的数据和下一个节点的指针，最后一个节点的指针为 null。

实现单链表的关键代码

单链表的核心是节点和节点之间的指针，所以我们需要先定义一个节点类（Node），包含节点元素（val）和指向下一个节点的指针（next）：

class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

然后我们需要定义单链表类（LinkedList），包含一个头节点（head）：

class LinkedList {
    Node head;

    // ...
}

接下来我们可以在单链表类中实现多种操作，这里介绍三种常用的操作：添加节点、删除节点、打印链表。

添加节点

向单链表中添加节点，需要经过以下步骤：

1. 创建新节点
2. 如果链表为空，头节点指向新节点
3. 如果链表不为空，遍历到链表尾部，在尾部添加新节点

代码如下：

public void addNode(int val) {
    Node node = new Node(val);

    if (head == null) {
        head = node;
    } else {
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

删除节点

从单链表中删除节点，需要经过以下步骤：

1. 遍历链表，找到需要删除的节点
2. 修改节点前一个节点的指针，指向需要删除节点的下一个节点

代码如下：

public void removeNode(int val) {
    if (head == null) {
        return;
    }

    if (head.val == val) {
        head = head.next;
        return;
    }

    Node cur = head;
    while (cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

打印链表

我们可以遍历整个单链表，输出每个节点的值。

代码如下：

public void printList() {
    Node cur = head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

示例说明

示例 1

LinkedList list = new LinkedList();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.printList(); // 输出 1 2 3

list.removeNode(2);
list.printList(); // 输出 1 3

我们先创建一个单链表，包含三个节点 1、2、3，然后输出链表。接着，我们删除节点 2，再次输出链表，可以看到节点 2 已经被删除。

示例 2

LinkedList list = new LinkedList();
list.addNode(1);
list.printList(); // 输出 1

list.addNode(2);
list.addNode(3);
list.printList(); // 输出 1 2 3

我们创建一个单链表，包含三个节点 1、2、3，然后输出链表。在此之前，我们先添加一个节点 1，输出链表，可以看到节点 1 已经被添加。接着，我们再添加两个节点 2 和 3，再次输出链表，确认节点已经被成功添加。

总结

通过以上代码示例，你已经学习到了如何使用 Java 实现简单的单链表，包括添加节点、删除节点和打印链表。接下来，可以尝试利用单链表来解决更多的算法问题。