在编码中避免不了使用链表，特别是循环链表，很多同学使用时为了省事直接使用C++ STL库中的链表实现，这样当然很简单也不容易出错，但同时也不可避免的带来了一些问题：
- 是半个黑盒，虽然能看源码，但是经过层层封装的STL源码很少有人愿意去认真看
- 随着C++版本的修改，部分特性可能会改变，可能会引入一些不必要的问题
因此有必要实现一款属于自己的双向链表，这样在有需要的时候就能随时增加自己的特性，让链表更好的服务于其他模块。
在使用C++实现链表时，我们需要实现两个主要的类：1. node节点类 ，2. 链接node节点的类
一般为了实现node的后期扩展，会将node实现成抽象类，后期根据自己需要进行扩展
class Node {
public:
~Node() = default;
};
然后在通过继承node类来实现自己链表中使用的node节点类
// 实现保存单个节点的链表
class NodeImpl : public Node {
public:
explicit NodeImpl(uint64_t sequence_number)
: sequence_number_(sequence_number) {}
uint64_t sequence_number() const { return sequence_number_; }
private:
// 节点管理类中需要直接使用成员变量，这里将其声明为友元类
friend class TailList;
// 双向链表要有指向前方和后方的指针
NodeImpl* prev_{};
NodeImpl* next_{};
// 真正保存的数据
const uint64_t sequence_number_;
};
首先，我们看到NodeImpl类继承自基类Node，它作为链表中的实际节点实现。每个NodeImpl对象都包含了一个表示序列号的uint64_t类型成员变量sequence_number_，以及两个指向前驱和后继节点的双向指针prev_和next_。由于TailList类需要访问这些私有成员，因此NodeImpl将TailList声明为友元类以允许直接操作。
class TailList {
public:
TailList() : head_(0) {
// 将自己指向自己形成一个最小环
head_.prev_ = &head_;
head_.next_ = &head_;
}
// 如果自己指向自己说明是空的，没有任何节点数据
bool empty() const { return head_.next_ == &head_; }
NodeImpl* oldest() const {
return head_.next_;
}
NodeImpl* newest() const {
return head_.prev_;
}
// new 出一个node节点，并把对应的node放到链表结尾
NodeImpl* New(uint64_t sequence_number) {
auto* node = new NodeImpl(sequence_number);
// 生成一个节点，并将节点插入环装链表的尾部
node->next_ = &head_;
node->prev_ = head_.prev_;
node->prev_->next_ = node;
node->next_->prev_ = node;
return node;
}
// 清理链表中的节点
static void Delete(const NodeImpl* node) {
node->prev_->next_ = node->next_;
node->next_->prev_ = node->prev_;
delete node;
}
private:
// 双向链表的原点，默认不存储任何数据
NodeImpl head_;
};
接下来，TailList类负责维护整个循环链表的结构。初始化时，它创建一个头节点head_，该节点的前驱和后继均指向自身，形成一个空链表的“闭环”。通过empty()函数可以快速检查链表是否为空，只需看head_的下一个节点是否仍是指向自己即可。
链表提供了oldest()和newest()接口，分别用于获取链表中最旧（第一个加入）和最新（最后一个加入）的节点。核心方法New(uint64_t sequence_number)用于创建新节点并将新节点插入到链表的尾部，即每次新增节点都会成为新的末尾节点。这个方法巧妙地利用双向链表的特点，通过更新新节点及其相邻节点的前后指针来完成插入操作。
同时，Delete(const NodeImpl* node)静态方法用来安全地从链表中移除指定节点，并释放其内存资源。此方法同样通过调整被删除节点前后节点之间的链接关系，确保链表的连续性不受影响。
int main(int argc, char* argv[]) {
TailList list;
list.New(1);
list.New(2);
list.New(3);
list.New(3);
list.New(3);
list.New(3);
do {
auto lpNode = list.newest();
std::cout << lpNode->sequence_number() << std::endl;
TailList::Delete(lpNode);
} while (!list.empty());
return 0;
}
最后，在main()函数中，我们展示了链表的实际应用。程序首先创建了一个TailList对象，并连续调用New()方法添加了几个具有不同序列号的节点。然后，通过一个do-while循环不断地找到链表中的最新节点，输出其序列号，并通过Delete()方法删除它，直到链表为空为止。
//
// Created by wangyz38535 on 2024/4/24.
//
#include <iostream>
// 尾插式循环链表
class TailList;
class Node {
public:
~Node() = default;
};
// 实现保存单个节点的链表
class NodeImpl : public Node {
public:
explicit NodeImpl(uint64_t sequence_number)
: sequence_number_(sequence_number) {}
uint64_t sequence_number() const { return sequence_number_; }
private:
// 节点管理类中需要直接使用成员变量，这里将其声明为友元类
friend class TailList;
// 双向链表要有指向前方和后方的指针
NodeImpl* prev_{};
NodeImpl* next_{};
// 真正保存的数据
const uint64_t sequence_number_;
};
class TailList {
public:
TailList() : head_(0) {
// 将自己指向自己形成一个最小环
head_.prev_ = &head_;
head_.next_ = &head_;
}
// 如果自己指向自己说明是空的，没有任何节点数据
bool empty() const { return head_.next_ == &head_; }
NodeImpl* oldest() const {
return head_.next_;
}
NodeImpl* newest() const {
return head_.prev_;
}
// new 出一个node节点，并把对应的node放到链表结尾
NodeImpl* New(uint64_t sequence_number) {
auto* node = new NodeImpl(sequence_number);
// 生成一个节点，并将节点插入环装链表的尾部
node->next_ = &head_;
node->prev_ = head_.prev_;
node->prev_->next_ = node;
node->next_->prev_ = node;
return node;
}
// 清理链表中的节点
static void Delete(const NodeImpl* node) {
node->prev_->next_ = node->next_;
node->next_->prev_ = node->prev_;
delete node;
}
private:
// 双向链表的原点，默认不存储任何数据
NodeImpl head_;
};
int main(int argc, char* argv[]) {
TailList list;
list.New(1);
list.New(2);
list.New(3);
list.New(3);
list.New(3);
list.New(3);
do {
auto lpNode = list.newest();
std::cout << lpNode->sequence_number() << std::endl;
TailList::Delete(lpNode);
} while (!list.empty());
return 0;
}
总结起来，这段代码提供了一个简洁而实用的尾插式循环链表的实现，适用于需要高效进行顺序添加和按最近添加顺序删除元素的场景。通过合理的封装和设计，使得链表的操作既直观又易于维护。
