java单向链表的实现实例

Java单向链表是一种非常常见的数据结构，它可以用于存储一系列的节点数据并进行相关操作。本攻略将会详细讲解Java单向链表的实现实例，其中包括链表的构造、插入、删除等操作。

一、定义链表节点类

首先，我们需要定义链表节点类，用于存储每个节点的数据以及指向下一个节点的指针。代码如下：

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

其中，val表示节点存储的数据，next表示指向下一个节点的指针。

二、创建链表

创建一个单向链表需要先定义一个头节点，然后不断地向头节点之后插入新的节点。代码如下：

ListNode head = new ListNode(0); // 定义头节点
ListNode cur = head;
for (int i = 1; i <= 5; i++) {
    ListNode node = new ListNode(i);
    cur.next = node;
    cur = cur.next;
}

上述代码中，首先定义了一个值为0的节点作为头节点，然后循环5次向链表中插入节点，每个节点的值从1到5递增。

三、插入节点

向单向链表中插入节点可以分为两种情况：插入到链表的头部和插入到链表的中间。代码如下：

1. 插入到链表的头部

ListNode node = new ListNode(6);
node.next = head.next;
head.next = node;

这里我们先新建一个节点，然后把新节点的指针指向链表的第一个节点。最后，把头节点的指针指向新节点，这样就完成了节点的插入操作。

2. 插入到链表的中间

假设我们要向上述链表中插入一个值为3的节点，代码如下：

ListNode node = new ListNode(3);
ListNode cur = head;
while (cur.next != null && cur.next.val < node.val) {
    cur = cur.next;
}
node.next = cur.next;
cur.next = node;

首先，新建一个节点并设置节点值。然后从头节点开始遍历链表，找到插入位置，即找到第一个节点值大于要插入节点值的节点位置。最后，插入节点，并调整节点指针，完成节点插入操作。

四、删除节点

从单向链表中删除某个节点需要遍历整个链表寻找待删除节点的前一个节点。代码如下：

int val = 3; // 待删除节点值
ListNode cur = head;
while (cur.next != null) {
    if (cur.next.val == val) {
        cur.next = cur.next.next;
        break;
    }
    cur = cur.next;
}

以上代码中，我们遍历整个链表，找到待删除节点的前一个节点。然后调整指针，忽略待删除节点，从而完成了节点的删除操作。

五、示例说明

示例一

我们要构造一个单向链表，值为1->2->3->4->5，并向链表中插入一个节点值为3的节点，代码如下：

ListNode head = new ListNode(0);
ListNode cur = head;
for (int i = 1; i <= 5; i++) {
    ListNode node = new ListNode(i);
    cur.next = node;
    cur = cur.next;
}

ListNode node = new ListNode(3);
cur = head;
while (cur.next != null && cur.next.val < node.val) {
    cur = cur.next;
}
node.next = cur.next;
cur.next = node;

以上代码中，首先定义头节点并循环向链表插入节点。然后，在遍历链表找到插入位置并插入节点。

示例二

我们构造一个值为1->2->3->4->5的单向链表，并从链表中删除一个节点值为3的节点。代码如下：

ListNode head = new ListNode(0);
ListNode cur = head;
for (int i = 1; i <= 5; i++) {
    ListNode node = new ListNode(i);
    cur.next = node;
    cur = cur.next;
}

int val = 3;
cur = head;
while (cur.next != null) {
    if (cur.next.val == val) {
        cur.next = cur.next.next;
        break;
    }
    cur = cur.next;
}

以上代码中，我们首先定义头节点并循环向链表插入节点。然后，遍历整个链表找到待删除节点的前一个节点，并调整指针完成了删除操作。

至此，我们完成了Java单向链表的实现实例的详细讲解。