前言

链表是计算机科学中最基础也是最重要的数据结构之一，它在C++开发中有着广泛的应用。本文将深入探讨链表的分类、实现方式以及各种应用场景，帮助我们在实际开发中做出更合理的数据结构选择。

1. 链表基础概念

链表是一种线性数据结构，它通过"节点"的方式来存储数据。每个节点包含两部分：数据域和指针域。不同于数组的连续内存分配，链表中的节点可以存储在内存的任意位置，通过指针连接形成一个完整的数据序列。

1.1 链表的基本特性

• 动态内存分配：链表可以根据需要动态地分配内存
• 非连续存储：节点在内存中的位置不要求连续
• 插入删除高效：不需要像数组那样移动大量元素
• 随机访问低效：必须从头节点开始遍历才能访问特定位置的节点

1.2 链表与数组的对比

特性	链表	数组
内存分配	动态分配，使用时分配	静态分配，编译时确定或运行时一次性分配
内存效率	需要额外的指针空间	紧凑连续，无额外开销
随机访问	O(n)	O(1)
插入删除	O(1)（已知位置的情况下）	O(n)（需要移动元素）
缓存局部性	较差	优秀

你是否曾经在项目中遇到过需要频繁插入删除操作的场景？在这种情况下，你会选择使用数组还是链表呢？

2. 链表的分类

根据节点之间的连接方式，链表可以分为以下几种类型：

2.1 单向链表（Singly Linked List）

单向链表是最基本的链表形式，每个节点包含数据和一个指向下一个节点的指针。

特点：

• 只能从头到尾遍历
• 删除节点需要知道其前驱节点
• 内存开销较小

实现示例：

#include <iostream>
#include <memory>

class SinglyLinkedList {
private:
    struct Node {
        int data;
        std::unique_ptr<Node> next;
        
        Node(int value) : data(value), next(nullptr) {}
    };
    
    std::unique_ptr<Node> head;
    
public:
    SinglyLinkedList() : head(nullptr) {}
    
    // 在链表头部插入节点
    void pushFront(int value) {
        auto newNode = std::make_unique<Node>(value);
        newNode->next = std::move(head);
        head = std::move(newNode);
    }
    
    // 在链表尾部插入节点
    void pushBack(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            return;
        }
        
        Node* current = head.get();
        while (current->next) {
            current = current->next.get();
        }
        
        current->next = std::move(newNode);
    }
    
    // 删除第一个值为value的节点
    bool remove(int value) {
        if (!head) return false;
        
        if (head->data == value) {
            head = std::move(head->next);
            return true;
        }
        
        Node* current = head.get();
        while (current->next && current->next->data != value) {
            current = current->next.get();
        }
        
        if (current->next) {
            current->next = std::move(current->next->next);
            return true;
        }
        
        return false;
    }
    
    // 打印链表
    void print() const {
        Node* current = head.get();
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next.get();
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    SinglyLinkedList list;
    
    list.pushBack(1);
    list.pushBack(2);
    list.pushBack(3);
    list.pushFront(0);
    
    std::cout << "原始链表: ";
    list.print();  // 输出: 0 -> 1 -> 2 -> 3 -> nullptr
    
    list.remove(2);
    std::cout << "删除值为2的节点后: ";
    list.print();  // 输出: 0 -> 1 -> 3 -> nullptr
    
    return 0;
}

执行结果：

应用场景：

• 实现栈数据结构
• 历史记录（如浏览器的后退功能）
• 简单的内存管理（如空闲内存块链表）
• 符号表管理

2.2 双向链表（Doubly Linked List）

双向链表中的每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。

特点：

• 可以双向遍历
• 删除节点不需要知道其前驱节点
• 内存开销较大
• 实现某些操作更高效（如在当前位置前插入节点）

实现示例：

#include <iostream>
#include <memory>

class DoublyLinkedList {
private:
    struct Node {
        int data;
        std::unique_ptr<Node> next;
        Node* prev;  // 使用原始指针避免循环引用
        
        Node(int value) : data(value), next(nullptr), prev(nullptr) {}
    };
    
    std::unique_ptr<Node> head;
    Node* tail;  // 尾指针，方便从尾部操作
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    
    // 在链表头部插入节点
    void pushFront(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            tail = head.get();
            return;
        }
        
        newNode->next = std::move(head);
        newNode->next->prev = newNode.get();
        head = std::move(newNode);
    }
    
    // 在链表尾部插入节点
    void pushBack(int value) {
        auto newNode = std::make_unique<Node>(value);
        
        if (!head) {
            head = std::move(newNode);
            tail = head.get();
            return;
        }
        
        newNode->prev = tail;
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
    
    // 删除第一个值为value的节点
    bool remove(int value) {
        if (!head) return false;
        
        if (head->data == value) {
            if (head.get() == tail) {
                tail = nullptr;
            } else {
                head->next->prev = nullptr;
            }
            
            head = std::move(head->next);
            return true;
        }
        
        Node* current = head.get();
        while (current && current->data != value) {
            current = current->next.get();
        }
        
        if (!current) return false;
        
        if (current == tail) {
            tail = current->prev;
            tail->next = nullptr;
        } else {
            current->next->prev = current->prev;
            current->prev->next = std::move(current->next);
        }
        
        return true;
    }
    
    // 从头到尾打印链表
    void printForward() const {
        Node* current = head.get();
        while (current) {
            std::cout << current->data << " <-> ";
            current = current->next.get();
        }
        std::cout << "nullptr" << std::endl;
    }
    
    // 从尾到头打印链表
    void printBackward() const {
        Node* current = tail;
        while (current) {
            std::cout << current->data << " <-> ";
            current = current->prev;
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    DoublyLinkedList list;
    
    list.pushBack(1);
    list.pushBack(2);
    list.pushBack(3);
    list.pushFront(0);
    
    std::cout << "正向遍历: ";
    list.printForward();  // 输出: 0 <-> 1 <-> 2 <-> 3 <-> nullptr
    
    std::cout << "反向遍历: ";
    list.printBackward();  // 输出: 3 <-> 2 <-> 1 <-> 0 <-> nullptr
    
    list.remove(2);
    std::cout << "删除值为2的节点后正向遍历: ";
    list.printForward();  // 输出: 0 <-> 1 <-> 3 <-> nullptr
    
    return 0;
}

执行结果：

应用场景：

• 需要双向遍历的场景（如文本编辑器）
• 实现LRU缓存（最近最少使用缓存）
• 浏览器的前进/后退功能
• 音乐播放器的播放列表（前一首/后一首）

你觉得在实现一个文本编辑器时，为什么双向链表比单向链表更适合？

2.3 循环链表（Circular Linked List）

循环链表是一种特殊的链表，其最后一个节点指向第一个节点，形成一个环。循环链表可以是单向的，也可以是双向的。

特点：

• 没有明确的开始和结束节点
• 从任意节点出发都可以遍历整个链表
• 适合需要循环处理的场景

实现示例（单向循环链表）：

#include <iostream>
#include <memory>

class CircularLinkedList {
private:
    struct Node {
        int data;
        std::shared_ptr<Node> next;  // 使用shared_ptr处理循环引用
        
        Node(int value) : data(value), next(nullptr) {}
    };
    
    std::shared_ptr<Node> head;
    
public:
    CircularLinkedList() : head(nullptr) {}
    
    // 在链表尾部插入节点
    void insert(int value) {
        auto newNode = std::make_shared<Node>(value);
        
        if (!head) {
            head = newNode;
            head->next = head;  // 指向自身形成循环
            return;
        }
        
        std::shared_ptr<Node> current = head;
        while (current->next != head) {
            current = current->next;
        }
        
        current->next = newNode;
        newNode->next = head;  // 新节点指向头节点形成循环
    }
    
    // 删除第一个值为value的节点
    bool remove(int value) {
        if (!head) return false;
        
        // 如果只有一个节点
        if (head->next == head) {
            if (head->data == value) {
                head = nullptr;
                return true;
            }
            return false;
        }
        
        // 如果要删除的是头节点
        if (head->data == value) {
            std::shared_ptr<Node> current = head;
            while (current->next != head) {
                current = current->next;
            }
            
            current->next = head->next;
            head = head->next;
            return true;
        }
        
        // 删除中间节点
        std::shared_ptr<Node> current = head;
        while (current->next != head && current->next->data != value) {
            current = current->next;
        }
        
        if (current->next != head) {
            current->next = current->next->next;
            return true;
        }
        
        return false;
    }
    
    // 打印链表（从头节点开始，遍历一圈）
    void print() const {
        if (!head) {
            std::cout << "空链表" << std::endl;
            return;
        }
        
        std::shared_ptr<Node> current = head;
        do {
            std::cout << current->data << " -> ";
            current = current->next;
        } while (current != head);
        
        std::cout << "(回到头节点: " << head->data << ")" << std::endl;
    }
};

int main() {
    CircularLinkedList list;
    
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    
    std::cout << "原始循环链表: ";
    list.print();  // 输出: 1 -> 2 -> 3 -> 4 -> (回到头节点: 1)
    
    list.remove(2);
    std::cout << "删除值为2的节点后: ";
    list.print();  // 输出: 1 -> 3 -> 4 -> (回到头节点: 1)
    
    list.remove(1);  // 删除头节点
    std::cout << "删除头节点后: ";
    list.print();  // 输出: 3 -> 4 -> (回到头节点: 3)
    
    return 0;
}

执行结果：

应用场景：

• 轮询调度算法（Round-Robin）
• 循环缓冲区
• 操作系统中的进程调度
• 多人游戏中的回合制系统

2.4 跳跃链表（Skip List）

跳跃链表是一种可以实现快速查找的数据结构，它通过在链表的基础上添加多级索引来加速查找过程。

特点：

• 平均查找时间为O(log n)
• 插入和删除操作也是O(log n)
• 实现相对复杂
• 空间复杂度为O(n)

实现示例：

#include <iostream>
#include <vector>
#include <memory>
#include <cstdlib>
#include <ctime>
#include <limits>

class SkipList {
private:
    static constexpr int MAX_LEVEL = 16;  // 最大层数
    static constexpr float P = 0.5f;      // 层级提升概率
    
    struct Node {
        int data;
        std::vector<std::shared_ptr<Node>> forward;  // 每层的前向指针
        
        Node(int value, int level) : data(value), forward(level, nullptr) {}
    };
    
    std::shared_ptr<Node> head;  // 头节点
    int level;                   // 当前最大层级
    
    // 随机生成层数
    int randomLevel() {
        int lvl = 1;
        while ((static_cast<float>(std::rand()) / RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
public:
    SkipList() : level(1) {
        // 使用最小值创建头节点
        head = std::make_shared<Node>(std::numeric_limits<int>::min(), MAX_LEVEL);
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
    }
    
    // 查找节点
    bool search(int value) const {
        std::shared_ptr<Node> current = head;
        
        // 从最高层开始查找
        for (int i = level - 1; i >= 0; i--) {
            // 在当前层向前移动，直到下一个节点的值大于等于目标值
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
        }
        
        // 移动到第0层的下一个节点
        current = current->forward[0];
        
        // 检查是否找到目标值
        return current && current->data == value;
    }
    
    // 插入节点
    void insert(int value) {
        std::vector<std::shared_ptr<Node>> update(MAX_LEVEL, head);
        std::shared_ptr<Node> current = head;
        
        // 从最高层开始查找插入位置
        for (int i = level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        
        // 移动到第0层的下一个节点
        current = current->forward[0];
        
        // 如果当前节点不存在或者值不等于要插入的值，则创建新节点
        if (!current || current->data != value) {
            int newLevel = randomLevel();
            
            // 如果新层级大于当前层级，更新头节点的前向指针
            if (newLevel > level) {
                for (int i = level; i < newLevel; i++) {
                    update[i] = head;
                }
                level = newLevel;
            }
            
            // 创建新节点
            auto newNode = std::make_shared<Node>(value, newLevel);
            
            // 更新指针
            for (int i = 0; i < newLevel; i++) {
                newNode->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = newNode;
            }
        }
    }
    
    // 删除节点
    bool remove(int value) {
        std::vector<std::shared_ptr<Node>> update(MAX_LEVEL, nullptr);
        std::shared_ptr<Node> current = head;
        
        // 从最高层开始查找要删除的节点
        for (int i = level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->data < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        
        current = current->forward[0];
        
        // 如果找到了要删除的节点
        if (current && current->data == value) {
            // 更新所有层的指针
            for (int i = 0; i < level; i++) {
                if (update[i]->forward[i] != current) {
                    break;
                }
                update[i]->forward[i] = current->forward[i];
            }
            
            // 更新层级
            while (level > 1 && !head->forward[level - 1]) {
                level--;
            }
            
            return true;
        }
        
        return false;
    }
    
    // 打印跳跃链表
    void print() const {
        for (int i = level - 1; i >= 0; i--) {
            std::cout << "Level " << i << ": ";
            std::shared_ptr<Node> node = head->forward[i];
            while (node) {
                std::cout << node->data << " -> ";
                node = node->forward[i];
            }
            std::cout << "nullptr" << std::endl;
        }
    }
};

int main() {
    SkipList skipList;
    
    skipList.insert(3);
    skipList.insert(6);
    skipList.insert(7);
    skipList.insert(9);
    skipList.insert(12);
    skipList.insert(19);
    skipList.insert(17);
    skipList.insert(26);
    skipList.insert(21);
    skipList.insert(25);
    
    std::cout << "跳跃链表结构:" << std::endl;
    skipList.print();
    
    std::cout << "\n查找操作:" << std::endl;
    std::cout << "查找 19: " << (skipList.search(19) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 15: " << (skipList.search(15) ? "找到" : "未找到") << std::endl;
    
    std::cout << "\n删除操作:" << std::endl;
    skipList.remove(19);
    std::cout << "删除 19 后:" << std::endl;
    skipList.print();
    
    return 0;
}

执行结果：

应用场景：

• 高效的查找操作（如数据库索引）
• Redis中的有序集合（Sorted Set）
• 需要快速查找和维护有序数据的场景

3. 链表的高级应用

3.1 自定义内存分配器

链表可以用于实现自定义内存分配器，管理内存池中的空闲块。

#include <iostream>
#include <cstddef>
#include <vector>

class SimpleMemoryPool {
private:
    struct MemoryBlock {
        size_t size;           // 内存块大小
        bool isFree;           // 是否空闲
        MemoryBlock* next;     // 指向下一个内存块
        void* data;            // 实际数据的起始位置
        
        MemoryBlock(size_t blockSize) : size(blockSize), isFree(true), next(nullptr) {}
    };
    
    void* poolStart;          // 内存池起始位置
    size_t poolSize;          // 内存池总大小
    MemoryBlock* freeList;    // 空闲块链表
    
public:
    SimpleMemoryPool(size_t size) : poolSize(size) {
        // 分配内存池
        poolStart = ::operator new(size);
        
        // 创建初始内存块
        freeList = new MemoryBlock(size);
        freeList->data = poolStart;
    }
    
    ~SimpleMemoryPool() {
        // 释放内存池
        ::operator delete(poolStart);
        
        // 释放内存块管理结构
        MemoryBlock* current = freeList;
        while (current) {
            MemoryBlock* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // 分配内存
    void* allocate(size_t size) {
        // 对齐大小（简化版本）
        size = (size + 7) & ~7;  // 8字节对齐
        
        MemoryBlock* prev = nullptr;
        MemoryBlock* current = freeList;
        
        // 查找足够大的空闲块
        while (current) {
            if (current->isFree && current->size >= size) {
                // 找到合适的块
                
                // 如果块足够大，可以分割
                if (current->size > size + sizeof(MemoryBlock) + 8) {
                    // 创建新的空闲块
                    MemoryBlock* newBlock = new MemoryBlock(current->size - size - sizeof(MemoryBlock));
                    newBlock->data = static_cast<char*>(current->data) + size;
                    
                    // 更新当前块
                    current->size = size;
                    
                    // 插入新块到链表
                    newBlock->next = current->next;
                    current->next = newBlock;
                }
                
                // 标记为已使用
                current->isFree = false;
                
                return current->data;
            }
            
            prev = current;
            current = current->next;
        }
        
        // 没有找到合适的块
        return nullptr;
    }
    
    // 释放内存
    void deallocate(void* ptr) {
        if (!ptr) return;
        
        MemoryBlock* current = freeList;
        
        // 查找包含此指针的块
        while (current) {
            if (current->data == ptr) {
                // 标记为空闲
                current->isFree = true;
                
                // 合并相邻的空闲块（简化版本）
                mergeAdjacentFreeBlocks();
                return;
            }
            current = current->next;
        }
    }
    
    // 合并相邻的空闲块
    void mergeAdjacentFreeBlocks() {
        MemoryBlock* current = freeList;
        
        while (current && current->next) {
            if (current->isFree && current->next->isFree) {
                // 合并两个块
                current->size += current->next->size + sizeof(MemoryBlock);
                
                // 移除下一个块
                MemoryBlock* toDelete = current->next;
                current->next = toDelete->next;
                delete toDelete;
            } else {
                current = current->next;
            }
        }
    }
    
    // 打印内存池状态（用于调试）
    void printStatus() const {
        MemoryBlock* current = freeList;
        int blockCount = 0;
        
        std::cout << "内存池状态:" << std::endl;
        while (current) {
            std::cout << "块 " << blockCount++ << ": ";
            std::cout << "大小 = " << current->size << " 字节, ";
            std::cout << "状态 = " << (current->isFree ? "空闲" : "已使用") << std::endl;
            current = current->next;
        }
    }
};

int main() {
    // 创建一个1KB的内存池
    SimpleMemoryPool pool(1024);
    
    std::cout << "初始状态:" << std::endl;
    pool.printStatus();
    
    // 分配一些内存
    void* p1 = pool.allocate(100);
    void* p2 = pool.allocate(200);
    void* p3 = pool.allocate(300);
    
    std::cout << "\n分配后状态:" << std::endl;
    pool.printStatus();
    
    // 释放一些内存
    pool.deallocate(p2);
    
    std::cout << "\n释放p2后状态:" << std::endl;
    pool.printStatus();
    
    // 再次分配
    void* p4 = pool.allocate(150);
    
    std::cout << "\n再次分配后状态:" << std::endl;
    pool.printStatus();
    
    return 0;
}

3.2 LRU缓存实现

使用双向链表和哈希表实现高效的LRU（最近最少使用）缓存。

#include <iostream>
#include <unordered_map>
#include <memory>

template<typename K, typename V>
class LRUCache {
private:
    struct Node {
        K key;
        V value;
        Node* prev;
        Node* next;
        
        Node(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;                          // 缓存容量
    Node* head;                            // 头节点（最近使用）
    Node* tail;                            // 尾节点（最久未使用）
    std::unordered_map<K, Node*> cache;    // 哈希表，用于O(1)查找
    
    // 将节点移动到链表头部（标记为最近使用）
    void moveToHead(Node* node) {
        if (node == head) return;
        
        // 从当前位置移除
        if (node == tail) {
            tail = node->prev;
            tail->next = nullptr;
        } else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        
        // 插入到头部
        node->next = head;
        node->prev = nullptr;
        head->prev = node;
        head = node;
    }
    
    // 添加新节点到头部
    void addToHead(Node* node) {
        if (!head) {
            head = tail = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
        }
    }
    
    // 移除尾部节点（最久未使用）
    void removeTail() {
        if (!tail) return;
        
        Node* oldTail = tail;
        
        if (head == tail) {
            head = tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        
        cache.erase(oldTail->key);
        delete oldTail;
    }
    
public:
    LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
    
    ~LRUCache() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // 获取值，如果存在则将其标记为最近使用
    V get(K key) {
        if (cache.find(key) == cache.end()) {
            throw std::runtime_error("Key not found");
        }
        
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    // 检查键是否存在
    bool contains(K key) {
        return cache.find(key) != cache.end();
    }
    
    // 插入或更新值
    void put(K key, V value) {
        if (cache.find(key) != cache.end()) {
            // 更新现有节点
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            // 创建新节点
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            
            // 如果超出容量，移除最久未使用的节点
            if (cache.size() > capacity) {
                removeTail();
            }
        }
    }
    
    // 打印缓存内容（从最近使用到最久未使用）
    void printCache() const {
        Node* current = head;
        std::cout << "LRU缓存内容 (最近使用 -> 最久未使用): ";
        while (current) {
            std::cout << "[" << current->key << ": " << current->value << "]";
            if (current->next) std::cout << " -> ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LRUCache<std::string, int> cache(3);
    
    cache.put("one", 1);
    cache.put("two", 2);
    cache.put("three", 3);
    
    std::cout << "初始缓存:" << std::endl;
    cache.printCache();  // [three: 3] -> [two: 2] -> [one: 1]
    
    // 访问已有元素
    std::cout << "\n获取 'one': " << cache.get("one") << std::endl;
    cache.printCache();  // [one: 1] -> [three: 3] -> [two: 2]
    
    // 添加新元素，超出容量
    cache.put("four", 4);
    std::cout << "\n添加 'four' 后:" << std::endl;
    cache.printCache();  // [four: 4] -> [one: 1] -> [three: 3]
    
    // 检查被淘汰的元素
    std::cout << "\n'two' 是否存在: " << (cache.contains("two") ? "是" : "否") << std::endl;
    
    return 0;
}

3.3 多项式表示与计算

链表可以用于表示多项式，每个节点存储一个项的系数和指数。

#include <iostream>
#include <memory>
#include <sstream>
#include <cmath>

class Polynomial {
private:
    struct Term {
        double coefficient;  // 系数
        int exponent;        // 指数
        std::unique_ptr<Term> next;
        
        Term(double coef, int exp) : coefficient(coef), exponent(exp), next(nullptr) {}
    };
    
    std::unique_ptr<Term> head;
    
    // 插入项，保持指数降序
    void insertTerm(double coef, int exp) {
        if (std::abs(coef) < 1e-10) return;  // 忽略系数为0的项
        
        auto newTerm = std::make_unique<Term>(coef, exp);
        
        if (!head || exp > head->exponent) {
            // 插入到头部
            newTerm->next = std::move(head);
            head = std::move(newTerm);
            return;
        }
        
        // 查找插入位置
        Term* current = head.get();
        while (current->next && current->next->exponent > exp) {
            current = current->next.get();
        }
        
        // 如果已存在相同指数的项，合并系数
        if (current->exponent == exp) {
            current->coefficient += coef;
            // 如果合并后系数为0，移除该项
            if (std::abs(current->coefficient) < 1e-10) {
                if (current == head.get()) {
                    head = std::move(head->next);
                } else {
                    Term* prev = head.get();
                    while (prev->next.get() != current) {
                        prev = prev->next.get();
                    }
                    prev->next = std::move(current->next);
                }
            }
        } else if (current->next && current->next->exponent == exp) {
            current->next->coefficient += coef;
            // 如果合并后系数为0，移除该项
            if (std::abs(current->next->coefficient) < 1e-10) {
                current->next = std::move(current->next->next);
            }
        } else {
            // 插入新项
            newTerm->next = std::move(current->next);
            current->next = std::move(newTerm);
        }
    }
    
public:
    Polynomial() : head(nullptr) {}
    
    // 从字符串解析多项式
    static Polynomial parse(const std::string& str) {
        Polynomial poly;
        std::istringstream iss(str);
        
        double coef;
        char var;
        char op;
        int exp;
        
        while (iss >> coef) {
            if (iss.peek() == '*') {
                iss >> op >> var >> op >> exp;
                poly.insertTerm(coef, exp);
            } else {
                poly.insertTerm(coef, 0);  // 常数项
            }
            
            if (iss.peek() == '+' || iss.peek() == '-') {
                if (iss.peek() == '+') {
                    iss >> op;
                } else {
                    iss >> op;
                    iss >> coef;
                    coef = -coef;
                    if (iss.peek() == '*') {
                        iss >> op >> var >> op >> exp;
                        poly.insertTerm(coef, exp);
                    } else {
                        poly.insertTerm(coef, 0);  // 常数项
                    }
                }
            }
        }
        
        return poly;
    }
    
    // 加法运算
    Polynomial operator+(const Polynomial& other) const {
        Polynomial result;
        
        // 复制当前多项式的所有项
        Term* current = head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        // 添加另一个多项式的所有项
        current = other.head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // 减法运算
    Polynomial operator-(const Polynomial& other) const {
        Polynomial result;
        
        // 复制当前多项式的所有项
        Term* current = head.get();
        while (current) {
            result.insertTerm(current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        // 减去另一个多项式的所有项
        current = other.head.get();
        while (current) {
            result.insertTerm(-current->coefficient, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // 乘法运算
    Polynomial operator*(const Polynomial& other) const {
        Polynomial result;
        
        // 遍历当前多项式的所有项
        Term* term1 = head.get();
        while (term1) {
            // 遍历另一个多项式的所有项
            Term* term2 = other.head.get();
            while (term2) {
                // 计算乘积项
                double newCoef = term1->coefficient * term2->coefficient;
                int newExp = term1->exponent + term2->exponent;
                result.insertTerm(newCoef, newExp);
                
                term2 = term2->next.get();
            }
            
            term1 = term1->next.get();
        }
        
        return result;
    }
    
    // 计算多项式在给定x值处的值
    double evaluate(double x) const {
        double result = 0.0;
        Term* current = head.get();
        
        while (current) {
            result += current->coefficient * std::pow(x, current->exponent);
            current = current->next.get();
        }
        
        return result;
    }
    
    // 转换为字符串表示
    std::string toString() const {
        if (!head) return "0";
        
        std::ostringstream oss;
        Term* current = head.get();
        bool isFirst = true;
        
        while (current) {
            // 处理系数
            if (current->coefficient > 0) {
                if (!isFirst) oss << " + ";
            } else {
                if (isFirst) oss << "-";
                else oss << " - ";
            }
            
            double absCoef = std::abs(current->coefficient);
            
            // 处理指数
            if (current->exponent == 0) {
                // 常数项
                oss << absCoef;
            } else if (current->exponent == 1) {
                // 一次项
                if (std::abs(absCoef - 1.0) < 1e-10) {
                    oss << "x";
                } else {
                    oss << absCoef << "*x";
                }
            } else {
                // 高次项
                if (std::abs(absCoef - 1.0) < 1e-10) {
                    oss << "x^" << current->exponent;
                } else {
                    oss << absCoef << "*x^" << current->exponent;
                }
            }
            
            isFirst = false;
            current = current->next.get();
        }
        
        return oss.str();
    }
};

int main() {
    // 创建多项式 p1 = 3*x^2 + 2*x + 1
    Polynomial p1 = Polynomial::parse("3*x^2 + 2*x + 1");
    std::cout << "p1(x) = " << p1.toString() << std::endl;
    
    // 创建多项式 p2 = x^3 - 2*x + 5
    Polynomial p2 = Polynomial::parse("1*x^3 - 2*x + 5");
    std::cout << "p2(x) = " << p2.toString() << std::endl;
    
    // 多项式加法
    Polynomial sum = p1 + p2;
    std::cout << "p1(x) + p2(x) = " << sum.toString() << std::endl;
    
    // 多项式减法
    Polynomial diff = p1 - p2;
    std::cout << "p1(x) - p2(x) = " << diff.toString() << std::endl;
    
    // 多项式乘法
    Polynomial product = p1 * p2;
    std::cout << "p1(x) * p2(x) = " << product.toString() << std::endl;
    
    // 计算多项式在x=2处的值
    double x = 2.0;
    std::cout << "p1(" << x << ") = " << p1.evaluate(x) << std::endl;
    std::cout << "p2(" << x << ") = " << p2.evaluate(x) << std::endl;
    
    return 0;
}

4. 链表的性能优化

4.1 内存池优化

频繁的动态内存分配和释放会影响链表的性能。使用内存池可以显著提高链表操作的效率。

4.2 缓存友好的链表

传统链表的节点分散在内存中，缓存命中率低。可以通过以下方式优化：

1. 块状链表：每个节点包含多个元素，提高缓存局部性
2. 紧凑链表：将节点存储在连续内存区域中

4.3 无锁链表

在多线程环境中，使用无锁算法实现链表可以避免锁竞争，提高并发性能。

5. 链表的选择与实践建议

5.1 何时选择链表

• 需要频繁插入和删除元素
• 元素数量不确定或经常变化
• 不需要随机访问
• 内存空间有限，需要动态分配

5.2 何时避免使用链表

• 需要频繁的随机访问
• 数据量较小且固定
• 缓存局部性很重要的场景
• 内存开销敏感的场景

5.3 实践建议

1. 选择合适的链表类型：根据应用场景选择单向、双向或循环链表
2. 使用智能指针：避免内存泄漏和悬挂指针问题
3. 考虑使用标准库：C++ STL提供了std::forward_list和std::list等现成实现
4. 注意边界条件：处理空链表、单节点链表等特殊情况
5. 优化频繁操作：针对最常用的操作进行优化

6. 总结

链表作为一种基础数据结构，在C++开发中有着广泛的应用。通过本文的介绍，我们了解了不同类型链表的特点、实现方式和应用场景。在实际开发中，需要根据具体需求选择合适的链表类型，并考虑性能优化和内存管理等因素。

你在实际项目中是否使用过链表？遇到了哪些挑战？欢迎在评论区分享你的经验和见解！