C++ 双向循环链表类模版实例详解

C++ 双向循环链表类模版实例详解

什么是双向循环链表？

双向循环链表（Doubly Linked Loop）是一种链式数据结构。相比于单向链表，它可以在两个方向上遍历，每个节点不仅保存了下一个节点的指针，还保存了上一个节点的指针。双向循环链表具有以下特点：

• 双向循环链表的首尾节点连接起来，没有 NULL/None 节点。
• 节点保存了指向上一节点和下一节点的指针，可以双向遍历。
• 可以方便地实现插入、删除操作，但访问某个节点的时间复杂度依然是 O(n)。

如何实现 C++ 双向循环链表类模版？

下面是一个简单的 C++ 双向循环链表类模版实现。代码里有详细的注释，以及注明需要自己实现的方法。

template <typename T>
class DoublyLinkedList
{
private:
    struct Node
    {
        T data;            // 保存节点的数据
        Node *prev, *next; // 指向前一个节点和后一个节点的指针
        Node(T d = T(), Node *p = nullptr, Node *n = nullptr)
            : data(d), prev(p), next(n) {}
    };

    Node *head; // 链表头

public:
    // 构造函数，初始化链表头
    DoublyLinkedList() : head(nullptr)
    {
        // TODO: 实现构造函数
    }

    // 析构函数，删除链表所有节点
    ~DoublyLinkedList()
    {
        // TODO: 实现析构函数
    }

    // 获取链表的长度
    int size() const
    {
        // TODO: 实现 size 函数
        return 0;
    }

    // 在链表头部插入节点
    void insert_front(const T &d)
    {
        // TODO: 实现 insert_front 函数
    }

    // 在链表尾部插入节点
    void insert_back(const T &d)
    {
        // TODO: 实现 insert_back 函数
    }

    // 从链表头部删除节点
    void remove_front()
    {
        // TODO: 实现 remove_front 函数
    }

    // 从链表尾部删除节点
    void remove_back()
    {
        // TODO: 实现 remove_back 函数
    }

    // 打印整个链表
    void print() const
    {
        // TODO: 实现 print 函数
    }
};

实例说明一：使用双向循环链表实现 LRU 缓存

以下是使用上述双向循环链表类模版实现 LRU 缓存的完整代码示例。具体思路是用双向循环链表来维护缓存中各个元素的访问顺序，每次访问需要先找到元素到双向循环链表上的对应节点，然后将该节点移到链表头部，这样链表队尾的节点就是 LRU 元素，每次需要淘汰的就是队尾节点。

template <typename K, typename V>
class LRUCache
{
public:
    typedef std::pair<K, V> CacheEntry;

private:
    DoublyLinkedList<CacheEntry> cache_;
    std::unordered_map<K, typename DoublyLinkedList<CacheEntry>::Node *> map_;
    int capacity_;

    // 将元素移到链表头部
    void move_to_front(typename DoublyLinkedList<CacheEntry>::Node *node)
    {
        // 如果节点已经是头部，无需移动
        if (node == cache_.head)
            return;

        // 将节点从链表中摘除
        node->prev->next = node->next;
        node->next->prev = node->prev;

        // 将节点插入到链表头部
        node->next = cache_.head;
        node->prev = cache_.head->prev;
        node->prev->next = node;
        node->next->prev = node;
    }

public:
    LRUCache(int cap) : capacity_(cap) {}

    // 获取缓存元素的值
    V get(const K &key)
    {
        // 如果在 map_ 中没有找到对应节点，则返回空
        if (map_.find(key) == map_.end())
            return V();

        // 将对应节点移到链表头部，并返回节点的 value
        auto node = map_[key];
        move_to_front(node);
        return node->data.second;
    }

    // 插入（或更新）缓存元素
    void put(const K &key, const V &value)
    {
        // 如果元素已经存在，则先更新 value，然后将节点移到链表头部
        if (map_.find(key) != map_.end())
        {
            auto node = map_[key];
            node->data.second = value;
            move_to_front(node);
            return;
        }

        // 如果元素不存在，插入（或更新）到 map_ 和链表头部
        cache_.insert_front(std::make_pair(key, value));
        map_[key] = cache_.head;

        // 如果插入后缓存大小超过 capacity_，则淘汰队尾元素
        if (cache_.size() > capacity_)
        {
            auto node = cache_.head->prev;
            map_.erase(node->data.first);
            cache_.remove_back();
        }
    }

    // 打印缓存元素
    void print() const
    {
        cache_.print();
    }
};

实例说明二：使用双向循环链表实现高精度加法

以下是使用上述双向循环链表类模版实现高精度加法的完整代码示例。具体思路是将两个大整数的每一位按从低到高的顺序相加，在每一位相加后确定当前位的进位和留位。

template <int BASE>
class BigNumber
{
public:
    using Digit = unsigned char;
    using Node = typename DoublyLinkedList<Digit>::Node;

private:
    DoublyLinkedList<Digit> digits_;

public:
    BigNumber() { digits_.insert_front(0); }

    BigNumber(const BigNumber &rhs) { digits_ = rhs.digits_; }

    ~BigNumber() {}

    BigNumber operator+(const BigNumber &rhs) const
    {
        BigNumber res;
        Node *n1 = digits_.head->next, *n2 = rhs.digits_.head->next, *nr = res.digits_.head;

        int carry = 0;
        while (n1 || n2)
        {
            // 取出当前位
            Digit d1 = n1 ? n1->data : 0, d2 = n2 ? n2->data : 0;

            // 计算当前位的和以及新的进位
            Digit sum = d1 + d2 + carry;
            carry = sum / BASE;
            sum %= BASE;

            // 新建一个节点保存当前位的值，插入到 res 中
            nr = res.digits_.insert_back(sum);
            if (n1)
                n1 = n1->next;
            if (n2)
                n2 = n2->next;
        }

        // 如果还有进位，新建一个节点保存进位的值，插入到 res 中
        if (carry)
            res.digits_.insert_back(carry);

        return res;
    }

    void print() const
    {
        Node *n = digits_.head->prev;
        while (n && n != digits_.head)
        {
            std::cout << static_cast<int>(n->data);
            n = n->prev;
        }
        std::cout << std::endl;
    }
};