Java实现单链表基础操作

下面我来详细讲解“Java实现单链表基础操作”的完整攻略。

单链表简介

单链表是一种最简单的链式存储结构，其基本组成部分是结点，结点包括数据域和指针域，指针域用来指向下一个结点。单链表的优点是插入、删除数据方便，缺点是查询数据相对困难。

基础操作

单链表的基础操作包括创建链表、插入结点、删除结点、查询结点、遍历链表等。下面分别进行介绍。

创建链表

创建链表需要先定义结点类，再利用结点类创建链表。结点类中包含了数据域和指针域，代码如下：

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

定义好结点类之后，在创建链表的过程中，只需要依次插入结点即可。例如，我们要创建一个包含 5 个元素的链表，代码如下：

ListNode head = new ListNode(0); // 创建链表头结点
ListNode p = head; // 定义指针指向头结点

for (int i = 1; i < 5; i++) { // 循环创建 4 个结点
    ListNode node = new ListNode(i); // 创建结点
    p.next = node; // 将结点插入链表
    p = node; // 指针指向新插入的结点
}

插入结点

在链表中插入结点，是先找到要插入位置的前一个结点，再将新结点插入该位置。例如，我们要在链表中间插入一个结点，代码如下：

ListNode node = new ListNode(val); // 创建新结点
ListNode p = head; // 定义指针指向头结点

while (p.next != null && p.next.val < val) { // 寻找要插入位置的前一个结点
    p = p.next;
}

node.next = p.next; // 将新结点插入到链表中
p.next = node;

删除结点

在链表中删除结点，需要先找到要删除的结点的前一个结点，然后将其指针指向该结点的下一个结点。例如，我们要删除链表中值为 3 的结点，代码如下：

ListNode p = head; // 定义指针指向头结点

while (p.next != null && p.next.val != val) { // 寻找要删除结点的前一个结点
    p = p.next;
}

if (p.next != null && p.next.val == val) { // 删除结点
    p.next = p.next.next;
}

查询结点

在链表中查询结点，需要遍历整个链表，找到目标结点。例如，我们要查询链表中值为 2 的结点是否存在，代码如下：

ListNode p = head; // 定义指针指向头结点

while (p != null) {
    if (p.val == val) { // 找到目标结点
        return true;
    }
    p = p.next;
}

return false;

遍历链表

遍历链表就是将链表中的每个结点都访问一遍，可以输出结点中的值或者进行其他操作。例如，我们要输出链表中每个结点的值，代码如下：

ListNode p = head.next; // 定义指针指向第一个结点

while (p != null) {
    System.out.print(p.val + " "); // 输出结点中的值
    p = p.next;
}

示例

下面给出两个示例，分别是创建链表和删除结点的示例。

创建链表示例

假设我们要创建一个链表，包含以下 5 个元素： 1 -> 3 -> 5 -> 7 -> 9。下面是完整代码：

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    public ListNode createLinkedList() {
        ListNode head = new ListNode(0); // 创建链表头结点
        ListNode p = head; // 定义指针指向头结点

        for (int i = 1; i < 10; i += 2) { // 循环创建 5 个结点
            ListNode node = new ListNode(i); // 创建结点
            p.next = node; // 将结点插入链表
            p = node; // 指针指向新插入的结点
        }

        return head.next;
    }
}

删除结点示例

假设现在有一个链表，包含以下 5 个元素： 1 -> 3 -> 5 -> 7 -> 9。我们要删除其中值为 5 的结点。下面是完整代码：

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    public void deleteNode(ListNode head, int val) {
        ListNode p = head;

        while (p.next != null && p.next.val != val) { // 寻找要删除结点的前一个结点
            p = p.next;
        }

        if (p.next != null && p.next.val == val) { // 删除结点
            p.next = p.next.next;
        }
    }
}