简单的双向循环链表实现与使用指南

CnLinkedList：双向循环链表实现与使用指南

概述

CnLinkedList是一个轻量级的双向循环链表实现，具有自包含节点结构的特点。每个节点既作为数据载体，又负责维护链表的连接关系，无需额外的链表管理对象。这种设计使得链表操作高效且内存使用紧凑，适合需要频繁插入、删除节点的场景。

类定义与实现

class CnLinkedList
{
public:
    CnLinkedList() {
        m_pcPrev = this;
        m_pcNext = this;
    }
    virtual ~CnLinkedList() {}

    inline void InsertPrev(CnLinkedList* pcLinkedList) {
        pcLinkedList->m_pcPrev = m_pcPrev;
        pcLinkedList->m_pcNext = this;
        m_pcPrev->m_pcNext = pcLinkedList;
        m_pcPrev = pcLinkedList;
    }
    
    inline CnLinkedList* RemovePrev() {
        CnLinkedList* pcPrev = m_pcPrev;
        if (this != pcPrev) {
            m_pcPrev = pcPrev->m_pcPrev;
            pcPrev->m_pcPrev->m_pcNext = this;
        }
        pcPrev->m_pcPrev = pcPrev;
        pcPrev->m_pcNext = pcPrev;
        return pcPrev;
    }
    
    inline CnLinkedList* GetPrev() const { return m_pcPrev; }

    inline void InsertNext(CnLinkedList* pcLinkedList) {
        pcLinkedList->m_pcPrev = this;
        pcLinkedList->m_pcNext = m_pcNext;
        m_pcNext->m_pcPrev = pcLinkedList;
        m_pcNext = pcLinkedList;
    }
    
    inline CnLinkedList* RemoveNext() {
        CnLinkedList* pcNext = m_pcNext;
        if (this != m_pcNext) {
            m_pcNext = pcNext->m_pcNext;
            pcNext->m_pcNext->m_pcPrev = this;
        }
        pcNext->m_pcPrev = pcNext;
        pcNext->m_pcNext = pcNext;
        return pcNext;
    }
    
    inline CnLinkedList* GetNext() const { return m_pcNext; }

    void RemoveFromLinkedList() {
        // 无论链表长度如何，都更新前后节点的指针关系
        m_pcPrev->m_pcNext = m_pcNext;
        m_pcNext->m_pcPrev = m_pcPrev;
        
        // 将当前节点恢复为自循环状态
        m_pcPrev = this;
        m_pcNext = this;
    }

    u32 LinkedListSize() const {
        u32 dwSize = 1;
        CnLinkedList* pcTemp = m_pcNext;
        while (this != pcTemp) {
            dwSize++;
            pcTemp = pcTemp->m_pcNext;
        }
        return dwSize;
    }

private:
    CnLinkedList* m_pcPrev;
    CnLinkedList* m_pcNext;
};

核心功能解析

1. 构造函数

CnLinkedList() {
    m_pcPrev = this;
    m_pcNext = this;
}

初始化时，节点的m_pcPrev和m_pcNext均指向自身，形成一个单个节点的循环链表。

2. 插入操作

• InsertPrev: 在当前节点前插入新节点

  void InsertPrev(CnLinkedList* pcLinkedList)
  

• InsertNext: 在当前节点后插入新节点

  void InsertNext(CnLinkedList* pcLinkedList)
  

插入操作通过调整前后节点的指针关系来完成，时间复杂度为O(1)。

3. 删除操作

• RemovePrev: 移除当前节点的前一个节点并返回

  CnLinkedList* RemovePrev()
  

• RemoveNext: 移除当前节点的后一个节点并返回

  CnLinkedList* RemoveNext()
  

• RemoveFromLinkedList: 当前节点主动从链表中脱离

  void RemoveFromLinkedList()
  

删除操作会将被移除的节点重置为自循环状态，避免野指针问题，时间复杂度为O(1)。

4. 辅助方法

• GetPrev(): 获取前一个节点
• GetNext(): 获取后一个节点
• LinkedListSize(): 计算链表包含的节点总数，时间复杂度为O(n)

使用示例

1. 创建带数据的节点类

#include <iostream>
#include "CnLinkedList.h"

// 创建一个带数据的链表节点
class DataNode : public CnLinkedList {
public:
    int value;
    DataNode(int val) : value(val) {}
};

2. 链表遍历函数

// 打印链表内容（从指定节点开始遍历）
void printList(CnLinkedList* startNode) {
    if (!startNode) return;
    
    CnLinkedList* current = startNode;
    DataNode* dataNode = static_cast<DataNode*>(current);
    std::cout << "链表内容: " << dataNode->value;
    
    current = current->GetNext();
    while (current != startNode) {
        dataNode = static_cast<DataNode*>(current);
        std::cout << " -> " << dataNode->value;
        current = current->GetNext();
    }
    std::cout << " (循环结束)" << std::endl;
}

3. 主要操作示例

int main() {
    // 1. 创建节点
    DataNode* node1 = new DataNode(10);
    DataNode* node2 = new DataNode(20);
    DataNode* node3 = new DataNode(30);
    DataNode* node4 = new DataNode(40);

    std::cout << "初始节点1的值: " << node1->value << ", 链表长度: " << node1->LinkedListSize() << std::endl;

    // 2. 插入节点
    node1->InsertNext(node2);  // 在node1后插入node2
    std::cout << "插入node2后，node1的链表长度: " << node1->LinkedListSize() << std::endl;
    printList(node1);

    node2->InsertNext(node3);  // 在node2后插入node3
    node1->InsertPrev(node4);  // 在node1前插入node4
    std::cout << "插入node3和node4后，链表长度: " << node1->LinkedListSize() << std::endl;
    printList(node1);

    // 3. 移除节点
    CnLinkedList* removed = node1->RemoveNext();  // 移除node1的下一个节点（node2）
    std::cout << "移除node2后，链表长度: " << node1->LinkedListSize() << std::endl;
    printList(node1);
    std::cout << "被移除的节点值: " << static_cast<DataNode*>(removed)->value << std::endl;

    // 4. 节点自移除
    node4->RemoveFromLinkedList();  // node4主动从链表中移除
    std::cout << "node4自移除后，链表长度: " << node1->LinkedListSize() << std::endl;
    printList(node1);

    // 5. 遍历链表（从node3开始）
    std::cout << "从node3开始遍历: ";
    printList(node3);

    // 清理内存
    delete node1;
    delete node2;
    delete node3;
    delete node4;

    return 0;
}

4. 预期输出

初始节点1的值: 10, 链表长度: 1
插入node2后，node1的链表长度: 2
链表内容: 10 -> 20 (循环结束)
插入node3和node4后，链表长度: 4
链表内容: 10 -> 20 -> 30 -> 40 (循环结束)
移除node2后，链表长度: 3
链表内容: 10 -> 30 -> 40 (循环结束)
被移除的节点值: 20
node4自移除后，链表长度: 2
链表内容: 10 -> 30 (循环结束)
从node3开始遍历: 链表内容: 30 -> 10 (循环结束)

适用场景

• 需要频繁在任意位置插入/删除节点的场景（如游戏对象管理、事件队列）
• 需支持双向遍历的链表结构
• 内存受限环境（无额外链表管理对象，节点自包含）

使用建议

1. 通过继承CnLinkedList实现具体的数据节点类
2. 遍历链表时，可从任意节点出发，通过GetNext()循环访问，直到回到起点
3. 节点销毁前建议调用RemoveFromLinkedList()，避免链表结构被破坏
4. 对于大型链表，LinkedListSize()方法效率较低，可考虑维护一个单独的长度计数器

CnLinkedList以极简的代码提供了双向循环链表的核心功能，适合对性能和内存使用有要求的场景。