什么是链表（Linked List）

一、链表介绍

链表（Linked List）是一种线性数据结构，由一组节点组成，每个节点包含数据元素和指向下一个节点的引用（或指针）。链表不同于数组，数组中的元素是按顺序存储在内存中的，而链表中的元素是分散存储的，每个元素通过指针连接。

1.1 链表的基本概念

链表是由一系列节点（Node）构成，每个节点包含：

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

链表的头节点（Head）是链表的入口，通常在操作链表时会通过头节点来遍历和操作链表。

1.2 链表的特点

动态大小：链表的大小可以根据需要动态增加或减少。
非连续存储：链表中的元素不是连续存储在内存中的。
插入和删除操作高效：在链表中插入或删除元素的时间复杂度是 O(1)，只需要修改相关指针即可。
随机访问困难：与数组不同，链表不支持直接通过索引访问元素，查找元素需要从头节点开始逐个遍历。

1.3 链表的分类

单向链表（Singly Linked List）：每个节点只包含指向下一个节点的指针。
双向链表（Doubly Linked List）：每个节点包含指向前一个节点和后一个节点的指针。
循环链表（Circular Linked List）：链表的尾节点指向头节点，形成一个环。

1.4 链表的优缺点

优点：

动态大小，内存利用率高。
在头部或中间插入、删除元素时，性能优越（O(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 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 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 reverse() {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextNode = current.next;  // 保存下一个节点
            current.next = prev;               // 当前节点指向前一个节点
            prev = current;                    // prev更新为当前节点
            current = nextNode;                // current移动到下一个节点
        }
        head = prev;  // 更新头节点
    }
}

// 测试链表操作
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

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

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

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

        // 反转链表
        list.reverse();
        System.out.println("反转后的链表：");
        list.printList(); // 输出：4 -> 3 -> 2 -> null
    }
}

代码分析：

ListNode类：定义链表节点的结构，包含一个整数数据域和一个指向下一个节点的指针（next）。
LinkedList类：定义链表的基本操作，包括插入、删除、查找、打印、反转等方法。
- insertAtHead(int data)：在链表头部插入一个新节点。
- insertAtTail(int data)：在链表尾部插入一个新节点。
- deleteNode(int value)：删除链表中指定值的节点。
- contains(int value)：检查链表中是否存在指定值的节点。
- printList()：打印链表中所有节点的值。
- reverse()：反转链表。
LinkedListDemo类：用于测试链表的各种操作。