当前位置：首页 > java >正文

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

java 2025/8/13 8:39:12

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后插入node2std::cout << "插入node2后，node1的链表长度: " << node1->LinkedListSize() << std::endl;printList(node1);node2->InsertNext(node3);  // 在node2后插入node3node1->InsertPrev(node4);  // 在node1前插入node4std::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 (循环结束)