链表的增删改查操作

链表作为一种灵活的线性数据结构，广泛应用于各类程序设计中，尤其是在需要频繁进行数据插入和删除的场景。今天我们将详细讲解链表中的增、删、改、查等常见操作。

一、链表的增操作

在链表中，插入元素主要有两种方式：在头部插入和在尾部插入。此外，我们也可以在链表的中间插入节点。插入操作的核心是修改指针，以确保新节点的正确连接。

1.1 在链表头部插入元素

在链表的头部插入新节点时，我们只需要将新节点的指针指向当前的头节点，然后更新头节点为新节点即可。

1.2 在链表尾部插入元素

在链表的尾部插入新节点时，我们需要遍历链表找到最后一个节点，然后将其 next 指针指向新节点。

1.3 在链表中间插入元素

在链表的中间插入元素时，需要遍历链表找到插入点的前一个节点，然后将前一个节点的指针指向新节点，新节点的指针指向原来的下一个节点。

二、链表的删操作

链表的删除操作是通过调整指针来完成的。我们只需要找到要删除的节点，并更新它前一个节点的指针，使其指向要删除节点的下一个节点即可。

2.1 删除头节点

删除链表头节点时，我们直接更新头节点为头节点的下一个节点。

2.2 删除尾节点

删除尾节点时，需要遍历链表，找到倒数第二个节点，并将其 next 指针设置为 null。

2.3 删除指定节点

删除指定节点时，遍历链表找到该节点的前一个节点，然后将前一个节点的 next 指针指向要删除节点的下一个节点。

三、链表的改操作

链表中的修改操作主要是针对节点数据的更新。我们可以通过查找某个节点，并修改该节点的 data 域来实现修改操作。

3.1 修改指定节点的数据

修改链表中某个节点的数据，首先需要通过遍历找到该节点，然后直接修改其 data 域的值。

四、链表的查操作

链表的查找操作主要是遍历链表，逐个检查每个节点的数据，直到找到目标节点为止。由于链表不支持通过索引直接访问元素，查找的时间复杂度通常为 O(n)。

4.1 查找链表中的指定元素

查找链表中是否包含某个元素，遍历链表，逐个节点检查数据域，直到找到目标节点或者遍历完整个链表。

五、链表的Java代码实现

下面，我们用 Java 代码来实现链表的增删改查操作。代码中包含了常见的链表操作，帮助大家更好地理解如何在实际编程中应用链表。

// 定义一个链表节点类
class ListNode {
    int data;        // 数据域，存储节点的值
    ListNode next;   // 指针域，指向下一个节点

    // 构造函数
    ListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

// 定义一个链表类
class LinkedList {
    ListNode head;  // 链表的头节点

    // 构造函数
    public LinkedList() {
        this.head = null;
    }

    // 在链表头部插入节点
    public void insertAtHead(int data) {
        ListNode newNode = new ListNode(data); // 创建新节点
        newNode.next = head;  // 新节点的next指向当前头节点
        head = newNode;       // 更新头节点为新节点
    }

    // 在链表尾部插入节点
    public void insertAtTail(int data) {
        ListNode newNode = new ListNode(data); // 创建新节点
        if (head == null) {  // 如果链表为空，将新节点作为头节点
            head = newNode;
        } else {
            ListNode current = head;  // 从头节点开始遍历
            while (current.next != null) { // 遍历到链表的最后一个节点
                current = current.next;
            }
            current.next = newNode;  // 将最后一个节点的next指向新节点
        }
    }

    // 在链表中间插入节点（指定位置插入）
    public void insertAtPosition(int data, int position) {
        ListNode newNode = new ListNode(data); // 创建新节点
        if (position == 0) {
            insertAtHead(data); // 如果插入位置是头部，直接调用插入头部的方法
            return;
        }
        ListNode current = head;
        int currentPosition = 0;
        // 遍历链表，找到插入位置的前一个节点
        while (current != null && currentPosition < position - 1) {
            current = current.next;
            currentPosition++;
        }
        if (current != null) {
            newNode.next = current.next;  // 新节点的next指向当前节点的下一个节点
            current.next = newNode;       // 当前节点的next指向新节点
        } else {
            System.out.println("插入位置超出链表范围");
        }
    }

    // 删除指定节点
    public void deleteNode(int value) {
        if (head == null) return; // 链表为空，返回

        // 如果删除的是头节点
        if (head.data == value) {
            head = head.next;
            return;
        }

        ListNode current = head;
        while (current.next != null && current.next.data != value) {
            current = current.next;  // 遍历链表，找到值为value的节点
        }

        if (current.next != null) {  // 如果找到了节点
            current.next = current.next.next;  // 删除该节点
        }
    }

    // 删除链表头节点
    public void deleteHead() {
        if (head != null) {
            head = head.next; // 直接将头节点指向下一个节点
        }
    }

    // 删除链表尾节点
    public void deleteTail() {
        if (head == null) return;  // 链表为空，返回

        // 如果链表只有一个节点，删除头节点就是删除尾节点
        if (head.next == null) {
            head = null;
            return;
        }

        ListNode current = head;
        // 遍历链表找到倒数第二个节点
        while (current.next != null && current.next.next != null) {
            current = current.next;
        }
        current.next = null;  // 将倒数第二个节点的next设置为null，删除尾节点
    }

    // 查找链表中是否包含某个值
    public boolean contains(int value) {
        ListNode current = head;
        while (current != null) {
            if (current.data == value) {
                return true;  // 找到节点，返回true
            }
            current = current.next;
        }
        return false;  // 没有找到节点，返回false
    }

    // 打印链表的所有节点
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null"); // 链表结束
    }

    // 修改指定节点的数据
    public void modifyNode(int oldValue, int newValue) {
        ListNode current = head;
        while (current != null) {
            if (current.data == oldValue) {
                current.data = newValue;  // 找到指定节点，修改数据
                return;
            }
            current = current.next;
        }
        System.out.println("未找到值为 " + oldValue + " 的节点");
    }
}

// 测试链表操作
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // 插入节点
        list.insertAtHead(1);  // 头插法：插入1
        list.insertAtHead(2);  // 头插法：插入2
        list.insertAtTail(3);  // 尾插法：插入3
        list.insertAtTail(4);  // 尾插法：插入4
        list.insertAtPosition(5, 2); // 在位置2插入5

        // 打印链表
        System.out.println("链表内容：");
        list.printList(); // 输出：2 -> 1 -> 5 -> 3 -> 4 -> null

        // 删除节点
        list.deleteNode(1);  // 删除值为1的节点
        System.out.println("删除值为1后的链表：");
        list.printList(); // 输出：2 -> 5 -> 3 -> 4 -> null

        // 删除头节点
        list.deleteHead();
        System.out.println("删除头节点后的链表：");
        list.printList(); // 输出：5 -> 3 -> 4 -> null

        // 删除尾节点
        list.deleteTail();
        System.out.println("删除尾节点后的链表：");
        list.printList(); // 输出：5 -> 3 -> null

        // 查找节点
        System.out.println("链表中是否包含值3：" + list.contains(3));  // 输出：true
        System.out.println("链表中是否包含值1：" + list.contains(1));  // 输出：false

        // 修改节点
        list.modifyNode(3, 6); // 修改值为3的节点为6
        System.out.println("修改值为3的节点后的链表：");
        list.printList(); // 输出：5 -> 6 -> null
    }
}