C++链表解析：从基础原理到高级应用，全面掌握链表的使用

// 单链表节点定义
template<typename T>
struct SingleListNode {
    T data;                           // 数据元素
    SingleListNode<T> *next;          // 指向下一个节点的指针
};
// 双链表节点定义
template<typename T>
struct DoubleListNode {
    T data;                           // 数据元素
    DoubleListNode<T> *prev;          // 指向前一个节点的指针
    DoubleListNode<T> *next;          // 指向下一个节点的指针
};

// 创建单链表节点
template<typename T>
SingleListNode<T> *createSingleListNode(const T &data) {
    SingleListNode<T> *newNode = new SingleListNode<T>;
    newNode->data = data;
    newNode->next = nullptr;
    return newNode;
}
// 创建双链表节点
template<typename T>
DoubleListNode<T> *createDoubleListNode(const T &data) {
    DoubleListNode<T> *newNode = new DoubleListNode<T>;
    newNode->data = data;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

#include <iostream>
#include <list>
int main() {
    std::list<int> lst;
    // 添加元素
    lst.push_back(1);
    lst.push_back(2);
    lst.push_front(0);
    // 使用迭代器访问元素
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    // 删除元素
    lst.pop_front();
    lst.pop_back();
    // 获取链表大小
    std::cout << "Size: " << lst.size() << std::endl;
    return 0;
}

template<typename T>
void reverseList(SingleListNode<T> *&head) {
    SingleListNode<T> *prev = nullptr;
    SingleListNode<T> *current = head;
    SingleListNode<T> *next = nullptr;
    while (current != nullptr) {
        next = current->next;  // 保存下一个节点的指针
        current->next = prev;  // 反转当前节点的指针
        prev = current;        // 更新prev指针
        current = next;        // 更新current指针
    }
    head = prev;  // 更新头节点指针
}

template<typename T>
struct SingleListNode {
    T data;
    std::unique_ptr<SingleListNode<T>> next;
};

std::list<std::pair<int, std::string>> lst;
lst.emplace_back(1, "one"); // 在尾部构造元素
lst.emplace_front(0, "zero"); // 在头部构造元素

template<typename T, bool IsDoublyLinked>
struct LinkedListNode {
    T data;
    std::unique_ptr<LinkedListNode<T, IsDoublyLinked>> next;
    if constexpr (IsDoublyLinked) {
        LinkedListNode<T, IsDoublyLinked>* prev;
    }
};

template<typename T>
struct SingleListNode {
    T data;
    std::unique_ptr<SingleListNode<T>> next;
};

template<typename T>
class LinkedList {
private:
    std::unique_ptr<SingleListNode<T>> head;
    SingleListNode<T>* tail;
    std::size_t size;
public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}
    // 插入、删除、查找等操作方法
    // ...省略部分代码
};

template<typename T>
class LinkedListIterator {
private:
    SingleListNode<T>* current;
public:
    explicit LinkedListIterator(SingleListNode<T>* node) : current(node) {}
    // 重载操作符
    T& operator*() {
        return current->data;
    }
    T* operator->() {
        return &(current->data);
    }
    // 前置自增操作符
    LinkedListIterator& operator++() {
        current = current->next.get();
        return *this;
    }
    // 后置自增操作符
    LinkedListIterator operator++(int) {
        LinkedListIterator temp(current);
        current = current->next.get();
        return temp;
    }
    bool operator==(const LinkedListIterator& other) const {
        return current == other.current;
    }
    bool operator!=(const LinkedListIterator& other) const {
        return current != other.current;
    }
};

template<typename T>
class LinkedList {
    // ...其他代码
public:
    // ...其他方法
    LinkedListIterator<T> begin() {
        return LinkedListIterator<T>(head.get());
    }
    LinkedListIterator<T> end() {
        return LinkedListIterator<T>(nullptr);
    }
};

#include <deque>
#include <iostream>
int main() {
    std::deque<int> d;
    // 在头部和尾部插入元素
    d.push_front(1);
    d.push_back(2);
    // 在指定位置插入元素
    d.insert(d.begin() + 1, 3);
    // 访问和修改元素
    d[0] = 4;
    d.at(1) = 5;
    // 使用迭代器遍历容器
    for (auto it = d.begin(); it != d.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;
    return 0;
}

#include <iostream>
#include <list>
#include <memory>
#include <stdexcept>
template <typename T>
class ObjectPool {
public:
    // 从对象池获取一个对象
    std::shared_ptr<T> acquire() {
        if (m_pool.empty()) {
            T* obj = new T();
            return std::shared_ptr<T>(obj, [this](T* p) { this->release(p); });
        } else {
            T* obj = m_pool.front();
            m_pool.pop_front();
            return std::shared_ptr<T>(obj, [this](T* p) { this->release(p); });
        }
    }
    // 将对象归还到对象池
    void release(T* obj) {
        m_pool.push_front(obj);
    }
    // 获取当前对象池中的对象数量
    size_t size() const {
        return m_pool.size();
    }
private:
    std::list<T*> m_pool;
};
class MyClass {
public:
    MyClass() {
        std::cout << "MyClass constructor called." << std::endl;
    }
    ~MyClass() {
        std::cout << "MyClass destructor called." << std::endl;
    }
    void doSomething() {
        std::cout << "MyClass::doSomething() called." << std::endl;
    }
};
int main() {
    ObjectPool<MyClass> my_class_pool;
    // 从对象池获取一个对象并使用它
    {
        auto obj = my_class_pool.acquire();
        obj->doSomething();
        std::cout << "Pool size: " << my_class_pool.size() << std::endl;
    }
    // 观察对象池中的对象数量变化
    std::cout << "Pool size after releasing the object: " << my_class_pool.size() << std::endl;
    // 再次从对象池获取对象
    {
        auto obj2 = my_class_pool.acquire();
        obj2->doSomething();
        std::cout << "Pool size: " << my_class_pool.size() << std::endl;
    }
    return 0;
}

#include <iostream>
#include <list>
#include <stdexcept>
#include <vector>
template <typename Key, typename Value>
class HashTable {
public:
    HashTable(size_t capacity = 10) : m_table(capacity) {}
    // 添加键值对
    void put(const Key& key, const Value& value) {
        size_t index = hash(key);
        for (const auto& pair : m_table[index]) {
            if (pair.first == key) {
                throw std::runtime_error("Key already exists.");
            }
        }
        m_table[index].push_back(std::make_pair(key, value));
    }
    // 获取键对应的值
    Value get(const Key& key) const {
        size_t index = hash(key);
        for (const auto& pair : m_table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        throw std::runtime_error("Key not found.");
    }
    // 删除键值对
    void remove(const Key& key) {
        size_t index = hash(key);
        for (auto it = m_table[index].begin(); it != m_table[index].end(); ++it) {
            if (it->first == key) {
                m_table[index].erase(it);
                return;
            }
        }
        throw std::runtime_error("Key not found.");
    }
private:
    size_t hash(const Key& key) const {
        // 简单的哈希函数示例，实际应用时请根据键类型实现适当的哈希函数
        return std::hash<Key>{}(key) % m_table.size();
    }
    std::vector<std::list<std::pair<Key, Value>>> m_table;
};
int main() {
    HashTable<std::string, int> hash_table;
    hash_table.put("one", 1);
    hash_table.put("two", 2);
    hash_table.put("three", 3);
    std::cout << "Value of key 'one': " << hash_table.get("one") << std::endl;
    std::cout << "Value of key 'two': " << hash_table.get("two") << std::endl;
    std::cout << "Value of key 'three': " << hash_table.get("three") << std::endl;
    hash_table.remove("one");
    try {
        std::cout << "Value of key 'one': " << hash_table.get("one") << std::endl;
    } catch (const std::runtime_error& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }
    return 0;
}

#include <iostream>
#include <memory>
#include <random>
#include <limits>
template <typename Key, typename Value>
class SkipList {
    static const int MAX_LEVEL = 32;
    struct Node {
        Key key;
        Value value;
        std::vector<std::shared_ptr<Node>> forward;
        Node(const Key& k, const Value& v, int level)
            : key(k), value(v), forward(level) {}
    };
public:
    SkipList() : m_header(std::make_shared<Node>(Key(), Value(), MAX_LEVEL)), m_level(1) {
        std::random_device rd;
        m_generator = std::mt19937(rd());
        m_distribution = std::uniform_int_distribution<int>(0, 1);
    }
    void insert(const Key& key, const Value& value) {
        std::vector<std::shared_ptr<Node>> update(m_level);
        auto x = m_header;
        for (int i = m_level - 1; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
        int level = random_level();
        if (level > m_level) {
            for (int i = m_level; i < level; ++i) {
                update.push_back(m_header);
            }
            m_level = level;
        }
        x = std::make_shared<Node>(key, value, level);
        for (int i = 0; i < level; ++i) {
            x->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = x;
        }
    }
    Value search(const Key& key) const {
        auto x = m_header;
        for (int i = m_level - 1; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key) {
                x = x->forward[i];
            }
        }
        x = x->forward[0];
        if (x && x->key == key) {
            return x->value;
        }
        throw std::runtime_error("Key not found.");
    }
    void remove(const Key& key) {
        std::vector<std::shared_ptr<Node>> update(m_level);
        auto x = m_header;
        for (int i = m_level - 1; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
        x = x->forward[0];
        if (x && x->key == key) {
            for (int i = 0; i < m_level; ++i) {
                if (update[i]->forward[i] != x) {
                    break;
                }
                update[i]->forward[i] = x->forward[i];
            }
            while (m_level > 1 && !m_header->forward[m_level - 1]) {
                --m_level;
            }
        } else {
            throw std::runtime_error("Key not found.");
        }
    }
private:
    int random_level() {
        int level = 1;
        while (m_distribution(m_generator) && level < MAX_LEVEL) {
            ++level;
        }
        return level;
    }
    std::shared_ptr<Node> m_header;
    int m_level;
    std::mt19937 m_generator;
std::uniform_int_distribution<int> m_distribution;
};
int main() {
SkipList<int, std::string> skip_list;
skip_list.insert(1, "one");
skip_list.insert(2, "two");
skip_list.insert(3, "three");
skip_list.insert(4, "four");
skip_list.insert(5, "five");
std::cout << "Search for key 1: " << skip_list.search(1) << std::endl;
std::cout << "Search for key 2: " << skip_list.search(2) << std::endl;
std::cout << "Search for key 3: " << skip_list.search(3) << std::endl;
skip_list.remove(2);
try {
    std::cout << "Search for key 2: " << skip_list.search(2) << std::endl;
} catch (const std::runtime_error& e) {
    std::cout << "Error: " << e.what() << std::endl;
}
return 0;