Java 单链表数据结构的增删改查教程

什么是单链表

单链表是一种常用的线性表，是链式存储结构，由多个结点组成，每个结点包含数据域和指针域，指针域指向下一个结点。单链表的优势在于可以在任意位置进行元素的插入和删除操作，但是在查询某个元素时，需要从头结点依次遍历，效率较低。

节点

单链表中的每一个元素称为节点，使用Java类进行表示

class Node {
    int val;  // 节点存储的元素值
    Node next; // 指向下一个节点的指针

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

创建链表

创建一个单链表需要一个头结点，头结点不存储任何元素值，只是为了方便操作。

class LinkedList {
    Node head; // 头结点

    public LinkedList() {
        this.head = new Node(0); // 初始化头结点
    }
}

插入节点

在单链表中插入一个元素需要知道要插入的位置和元素的值。插入操作的指针操作很重要，因为没有指针指向前一个节点，所以需要将待插入节点的指针指向下一个节点。

public void add(int val) {
    Node node = new Node(val);
    Node cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = node;
}

将一个节点插入某个位置时，需要先找到要插入位置的前一个节点，然后将它的指针指向新节点，新节点的指针指向后一个节点。

public void add(int index, int val) {
    Node node = new Node(val);
    Node cur = head;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    node.next = cur.next;
    cur.next = node;
}

示例：

LinkedList list = new LinkedList();
list.add(1);
list.add(3);
list.add(2);
list.add(4);
list.add(0, 5); // 在第一个位置插入元素5

删除节点

删除单链表中的一个元素需要知道要删除元素的位置，需要将该节点的前一个节点的指针指向该节点的后一个节点。

public void remove(int index) {
    Node cur = head;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
}

示例：

LinkedList list = new LinkedList();
list.add(1);
list.add(3);
list.add(2);
list.add(4);
list.remove(2); // 删除第三个元素

查询节点

查询单链表中的一个元素需要从头结点开始遍历，直到找到要查询的元素。如果单链表非常长，效率就会非常低。

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

示例：

LinkedList list = new LinkedList();
list.add(1);
list.add(3);
list.add(2);
list.add(4);
Node node = list.search(3); // 查询元素3