使用C++实现尾插式循环链表结构

在编码中避免不了使用链表，特别是循环链表，很多同学使用时为了省事直接使用C++ STL库中的链表实现，这样当然很简单也不容易出错，但同时也不可避免的带来了一些问题：

1. 是半个黑盒，虽然能看源码，但是经过层层封装的STL源码很少有人愿意去认真看
2. 随着C++版本的修改，部分特性可能会改变，可能会引入一些不必要的问题

因此有必要实现一款属于自己的双向链表，这样在有需要的时候就能随时增加自己的特性，让链表更好的服务于其他模块。

在使用C++实现链表时，我们需要实现两个主要的类：1. node节点类 ，2. 链接node节点的类

一般为了实现node的后期扩展，会将node实现成抽象类，后期根据自己需要进行扩展

class Node {
public:
    ~Node() = default;
};
1
2
3
4

然后在通过继承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_;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

首先，我们看到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_;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

接下来，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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后，在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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

总结起来，这段代码提供了一个简洁而实用的尾插式循环链表的实现，适用于需要高效进行顺序添加和按最近添加顺序删除元素的场景。通过合理的封装和设计，使得链表的操作既直观又易于维护。