链表 Linked List

链表是一种线性数据结构，它由多个节点（Node）组成，每个节点包含两部分：

数据部分：存储实际的数据。
指针部分：存储指向下一个节点的地址。

链表的结构特点是节点在内存中不一定是连续存储的，而是通过指针将一个个节点连接起来。每个节点可以通过指针找到下一个节点，形成一个链式结构。

链表的类型：

单向链表（Singly Linked List）：每个节点只包含指向下一个节点的指针，最后一个节点的指针指向 null。
双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和下一个节点，便于从两端遍历。
循环链表（Circular Linked List）：链表的最后一个节点的指针指向第一个节点，形成一个环。

链表的特点：

动态大小：链表大小可以动态调整，元素可以随时添加或删除，且不需要提前指定大小。
插入和删除操作高效：链表在任何位置的插入和删除都比数组更高效，因为只需要改变指针的指向即可。
访问不方便：链表的元素不是连续存储的，访问某个特定元素时需要从头遍历链表，效率较低。

链表的缺点：

随机访问差：在链表中，访问某个元素需要从头节点开始逐个遍历，无法像数组那样通过索引直接访问，效率较低。
额外内存开销：每个节点都需要额外的指针空间，增加了内存的消耗。
复杂的实现和维护：链表的插入、删除、遍历等操作涉及到指针操作，相比数组实现较复杂。

链表的操作：

插入操作：在链表的任意位置插入一个新节点，需要更新指针的连接。
删除操作：删除链表中的某个节点时，更新指针，使其跳过被删除的节点。
遍历操作：从头节点开始，顺序访问链表中的所有节点。
查找操作：遍历链表查找特定元素（通常时间复杂度是 O(n)）。

示例（C++）：

#include <iostream>
using namespace std;

// 定义链表节点结构
struct Node {
    int data;      // 存储数据
    Node* next;    // 指向下一个节点的指针
};

// 插入节点
void insert(Node*& head, int value) {
    Node* newNode = new Node();  // 创建新节点
    newNode->data = value;       // 设置数据
    newNode->next = head;        // 新节点指向当前头节点
    head = newNode;              // 更新头节点
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    Node* head = nullptr;  // 空链表

    // 插入元素
    insert(head, 10);
    insert(head, 20);
    insert(head, 30);

    // 打印链表
    printList(head);  // 输出: 30 20 10

    return 0;
}

在这个例子中，我们定义了一个链表节点 Node，每个节点包含一个 data 数据部分和一个 next 指针，指向下一个节点。通过 insert 函数将元素插入链表头部，并通过 printList 函数遍历链表输出元素。

链表的应用：

动态内存管理：链表的动态大小使其适用于内存不确定的场合，常用于实现内存分配器和垃圾回收。
实现队列和栈：链表可以用来实现队列（FIFO）和栈（LIFO）数据结构。
- 队列：使用链表的尾部进行插入，头部进行删除。
- 栈：使用链表的头部进行插入和删除。
图的邻接表：链表常用于图的邻接表表示，便于存储图中每个节点的邻接节点。
操作系统进程调度：链表可以用来实现操作系统的进程调度队列，支持动态添加和删除进程。