Java实现带头结点的单链表

下面我会详细讲解Java实现带头结点的单链表的完整攻略。整个过程分为以下几个步骤：

1. 定义单链表节点类

首先，我们需要定义一个节点类来表示单链表的节点。节点类需要包含以下两个属性：

• 数据域：用来存储节点中的数据。
• 指针域：指向下一个节点的指针。

以下是节点类的定义示例：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

在这个示例中，我们使用了一个整型数值 val 来存储节点中的数据，并定义了一个指针 next 指向下一个节点。注意，这里我们使用的是类的构造函数来初始化节点的数值域。

2. 定义单链表类

接下来，我们需要定义一个单链表类来管理节点。单链表类需要包含以下几个方法：

• 在链表尾部添加一个节点。
• 在链表中插入一个节点。
• 删除链表中的一个节点。
• 遍历整个链表并打印所有节点的值。

以下是单链表类的定义示例：

public class LinkedList {
    private ListNode head;  // 头节点

    // 在链表尾部添加一个节点
    public void addNode(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = node;
            return;
        }

        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    // 在链表中插入一个节点
    public void insertNode(int val, int index) {
        ListNode node = new ListNode(val);
        ListNode cur = head;
        int i = 0;
        while (cur != null && i < index) {
            cur = cur.next;
            i++;
        }
        if (cur == null) {
            return;
        }
        node.next = cur.next;
        cur.next = node;
    }

    // 删除链表中的一个节点
    public void deleteNode(int val) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null && cur.val != val) {
            prev = cur;
            cur = cur.next;
        }
        if (cur == null) {
            return;
        }
        if (prev == null) {
            head = cur.next;
        } else {
            prev.next = cur.next;
        }
    }

    // 遍历整个链表并打印所有节点的值
    public void printList() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

我们可以看到，在这个示例中，我们定义了一个私有的头节点 head ，并对应实现了上述四个函数方法。

3. 使用单链表

最后，我们可以使用上面定义的单链表类来实现一些基本操作。例如，我们可以创建一个新的链表对象，并向其中添加一个节点，然后遍历整个链表打印所有节点的值。

以下是一个使用示例：

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4);

        list.insertNode(5, 2);

        list.deleteNode(3);

        list.printList();
    }
}

在这个示例中，我们创建了一个空链表，并向其中依次添加了四个节点。然后，我们调用 insertNode 方法在第三个节点后面添加了一个新节点 5。接着，我们调用 deleteNode 方法删除了值为 3 的节点。最后，我们调用 printList 方法遍历整个链表并打印所有节点的值，输出结果如下：

1 2 5 4

类似地，我们可以使用单链表类实现更多的操作，例如在链表头部添加一个节点、在链表中查找一个节点等等。