什么是链表？

链表（Linked List）是一种数据结构，由一系列节点（Node）组成，每个节点包含两部分内容：

1. 数据（Data）：存储实际的数据元素。
2. 指针（Pointer）：指向链表中的下一个节点。

链表的基本特性是：

• 每个节点都有指向下一个节点的指针。
• 链表的元素不一定在内存中连续存储，而是通过指针进行连接。

链表与数组相比，最大的不同是：链表中的元素不必连续存储，且可以动态扩展或缩减。

链表的类型

1. 单向链表（Singly Linked List）：每个节点指向下一个节点，最后一个节点指向 null。
2. 双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向下一个节点和前一个节点。
3. 循环链表（Circular Linked List）：链表的尾节点指向头节点，形成一个环状结构。

链表和数组的区别

链表的基本操作

1. 插入操作：在链表的指定位置插入新节点。
2. 删除操作：删除指定位置的节点。
3. 查找操作：查找链表中是否存在某个数据元素。
4. 遍历操作：访问链表中的每个节点。

代码案例：单向链表实现

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

    // 构造方法
    public Node(int data) {
        this.data = data;
        this.next = null;  // 默认指针为空
    }
}

// 定义链表类
class LinkedList {
    Node head; // 链表的头节点

    // 构造方法
    public LinkedList() {
        head = null;  // 初始化时链表为空
    }

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

    // 遍历链表并打印每个节点的值
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 删除指定值的节点
    public void delete(int data) {
        if (head == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        // 如果要删除的是头节点
        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null && current.next.data != data) {
            current = current.next;
        }

        // 如果找到了目标节点，删除它
        if (current.next != null) {
            current.next = current.next.next;
        } else {
            System.out.println("未找到要删除的节点");
        }
    }

    // 查找指定值的节点
    public boolean find(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return true; // 找到节点
            }
            current = current.next;
        }
        return false; // 未找到节点
    }
}

// 主程序演示链表操作
public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.append(40);

        System.out.println("链表内容：");
        list.printList();  // 输出：10 -> 20 -> 30 -> 40 -> null

        System.out.println("删除节点 20:");
        list.delete(20);
        list.printList();  // 输出：10 -> 30 -> 40 -> null

        System.out.println("查找节点 30: " + list.find(30)); // 输出：true
        System.out.println("查找节点 50: " + list.find(50)); // 输出：false
    }
}

代码解析

• Node 类：定义了链表节点，每个节点包含 data 数据和 next 指向下一个节点的指针。
• LinkedList 类：定义了链表的基本操作，如 append（插入节点）、printList（打印链表）、delete（删除节点）和 find（查找节点）。
• 在 main 方法中，我们创建了一个链表对象，并进行插入、删除和查找操作。

总结

链表是一种灵活且动态的数据结构，相比数组在插入和删除操作上更具优势，但在访问元素时相对较慢。理解链表的结构及其操作是掌握数据结构和算法的基础。