数据结构：链表 (Linked List)

什么是链表？

链表是一种线性数据结构，但它不像数组那样在内存中连续存储。它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表的类型

• 单向链表: 每个节点只有一个指向下一个节点的指针。
• 双向链表: 每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
• 循环链表: 最后一个节点的指针指向第一个节点，形成一个环。

基本操作

• 插入: 在链表的特定位置添加一个新节点。O(1)（如果知道前驱节点）或 O(n)。
• 删除: 从链表中移除一个节点。O(1)（如果知道前驱节点）或 O(n)。
• 查找: 遍历链表寻找一个特定的值。O(n)。

C++ 实现一个简单的单向链表

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void print() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "NULL" << std::endl;
    }
};

优缺点

• 优点: 动态大小，插入和删除效率高（在已知位置时）。
• 缺点: 无法随机访问（必须从头遍历），需要额外的空间存储指针。