用 C++ 创建单向链表 forward list
文章目录
- 前言
- 1. 源码 forward_list.hpp
- 2. 使用示例
前言
用 C++ 创建了一个单向链表，用于练习使用现代 C++ 的特性，包括 3 点：
- 对于容器，使用 std::initializer_list 作为参数创建构造函数。
C++ Core Guidelines 中，推荐使用花括号 {} 初始化对象，并且对容器推荐使用 std::initializer_list 创建构造函数。 - 使用智能指针 unique_ptr 。
- 使用了 copy and move （即 copy and swap 惯用法的改进版）。
关于 copy and move ，可参见我的另一篇文章
《C++ 的 copy and swap 惯用法》https://blog.csdn.net/drin201312/article/details/149204977
1. 源码 forward_list.hpp
/*
自定义单向链表。包含功能：
1. 创建链表。
2. 头部插入元素，任意位置的前向插入。
3. 除最后一个元素之外，任意位置的后向插入。
4. 遍历链表并显示。
5. 根据输入位置，删除元素。
6. 根据输入的数值，删除链表中所有相同的元素。
7. 复制链表。
8. 清空链表。
*/#ifndef FORWARD_LIST_H_
#define FORWARD_LIST_H_
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <string>
#include <stack>
#include <utility>// 链表的节点。
template<typename T>
class Node {public:Node() = default;// 常函数如果返回引用，则必须返回 const 引用。const T& get_data() const { // 返回节点内的数据。return data_; }// 给节点输入数据。void set_data(const T& data) {data_ = data;}// 返回下一个节点地址的 reference。std::unique_ptr<Node<T>>& get_next_ptr() {return ptr_next_;}// 夺取下一个节点的 unique_ptrvoid set_next_ptr(std::unique_ptr<Node<T>>&& next_node_ptr) { ptr_next_ = std::move(next_node_ptr); }private:T data_{}; // 节点内的数据。整数会默认初始化为 0 。std::unique_ptr<Node<T>> ptr_next_; // 下一个节点的地址。
};template<typename T> // 必须设置 T，用作 Node 的类型。
class ForwardList {public: // 该部分必须考虑如何处理 7 个函数：4 个构造函数，2 个赋值操作符，1 个析构函数。ForwardList() = default; // 允许使用无括号 ForwardList foo 的形式创建对象。// 用 initializer_list 接收任意数量的参数。ForwardList(std::initializer_list<T> args) {std::cout << "Default initializer_list called.\n";// for (auto each : args | std::views::reverse) { // C++ 20 使用此方式逆序。// std::cout << "each= " << each << "\n";// push_front(each);// }// C++ 14 使用下面 std::rbegin 的方式逆序。for (auto it = std::rbegin(args); it != std::rend(args); ++it) {push_front(*it);}}// 拷贝构造函数，必须手动把链表复制过来。ForwardList(const ForwardList& other) { std::cout << "Copy constructor called.\n";if (other.nodes_quantity_ != 0) {std::stack<T> data_record; // 记录 other 中的所有 dataNode<T>* running_node_ptr{other.front_node_ptr_.get()};for (size_t index = 0; index < other.nodes_quantity_; ++index) {data_record.emplace(running_node_ptr->get_data());running_node_ptr = running_node_ptr->get_next_ptr().get();}while (!data_record.empty()) { // 根据记录的 data 新建整个链表。push_front(data_record.top());data_record.pop();}}}// 下面使用 copy and move 方法，把两个赋值运算符函数合二为一。// 转移 other 的资源，并且 other 应该是用 copy 或 move 新建的一个对象。void move_resource(ForwardList&& other) noexcept {std::cout << "move_resource called.\n";front_node_ptr_ = std::move(other.front_node_ptr_);nodes_quantity_ = other.nodes_quantity_;// 清理 other 中的资源。对于内置的数值类型， std::move 并不会将其归零，必须手动修改。other.nodes_quantity_ = 0;}// 移动构造函数，把链表资源转移到当前对象。ForwardList(ForwardList&& other) noexcept {std::cout << "Move constructor called.\n";// 初始化列表不能完成所有的转移工作，所以直接调用函数，不使用初始化列表。move_resource(std::move(other)); };// 赋值运算符，把拷贝赋值运算符和移动赋值运算符进行二合一，并且能避免自赋值问题。ForwardList& operator=(ForwardList other) { // other 必须用值传递。std::cout << "operator= called.\n";move_resource(std::move(other)); return *this;}~ForwardList() {clear(); }// 头部插入一个 node。void push_front(const T& data) { std::cout << "@push_front" << "\tdata= " << data << "\n";auto new_node_ptr = create_node(data); // 这里会进行 NRVO 。new_node_ptr->set_next_ptr(std::move(front_node_ptr_));// 每个新节点，都会成为首节点。front_node_ptr_ = std::move(new_node_ptr);}// 在指定 node 位置的后面再插入一个 node 。void insert_after(const size_t node_index, const T& data) { std::cout << "@insert_after, node_index= " << node_index << "\n";check_index(node_index); if (nodes_quantity_ == 0) {push_front(data);} else {auto new_node_ptr = create_node(data); // 这里会进行 NRVO 。Node<T>& current_node = goto_node(node_index);// 如果返回值是一个 reference，则该函数返回结果属于左值。// 下面两个输入参数都是左值，需用 std::move 转换为右值引用。new_node_ptr->set_next_ptr(std::move(current_node.get_next_ptr())); current_node.set_next_ptr(std::move(new_node_ptr));std::cout << "current_node.get_data()= " << current_node.get_data() << "\n";}}// 在指定 node 的位置，前面再插入一个 node 。void insert_before(size_t node_index, const T& data) { std::cout << "@insert_before, node_index= " << node_index << "\n";if (node_index == 0) {push_front(data);} else { // 第 n 个位置向前插入一个节点，等于第 n-1 位置向后插入一个节点。insert_after(node_index - 1, data);}}void show_list() const { // 显示整个链表。std::cout << "\nshowing the whole forward list: \n";if (nodes_quantity_ == 0) {std::cout << "Empty forward list.\n";} else {// 用到原始指针时，尽量缩小范围。因为只限于这个函数内部，生命周期极短，不会发生内存泄漏。Node<T>* running_node_ptr = front_node_ptr_.get();for (size_t i = 0; i < nodes_quantity_; ++i) {std::cout << "node[" << i << "].data= " << running_node_ptr->get_data() << "\n";running_node_ptr = running_node_ptr->get_next_ptr().get();}}}// 根据输入的位置 index ，删除元素。void delete_by_index(size_t node_index) {std::cout << "@delete_by_index, node_index= " << node_index << "\n";check_index(node_index); if (nodes_quantity_ != 0) { // 避开空链表。if (node_index == 0) {front_node_ptr_ = std::move(front_node_ptr_->get_next_ptr());} else { // 把前一个节点链接到后一个节点即可。Node<T>& previous_node = goto_node(node_index - 1);previous_node.set_next_ptr(std::move(previous_node.get_next_ptr()->get_next_ptr()));}--nodes_quantity_;}}// 根据输入的值，删除链表中所有具有相同值的 node 。void delete_by_value(const T& value) {std::cout << "@delete_by_value, value= " << value << "\n";std::stack<size_t> index_record; // 使用一个后进先出的容器来记录 index 。Node<T>* running_node_ptr = front_node_ptr_.get();for (size_t index = 0; index < nodes_quantity_; ++index) {if (running_node_ptr->get_data() == value) {index_record.emplace(index); // 记录当前 index。}running_node_ptr = running_node_ptr->get_next_ptr().get();}std::cout << "Found " << index_record.size() << " of " << value << "\n";while (!index_record.empty()) {size_t index = index_record.top(); // 先删除大的索引，再删除小的索引。index_record.pop(); // 必须同时删除对应的 index 。delete_by_index(index);}}// 返回链表的大小。size_t size() const {return nodes_quantity_;}// 清除链表数据。void clear() {std::cout << "@clear, clearing the whole forward list.\n";while (front_node_ptr_) { // unique_ptr 只要指向新的资源，原有资源就被释放。front_node_ptr_ = std::move(front_node_ptr_->get_next_ptr());}nodes_quantity_ = 0;}private:// 链表状态有变化时，下面两个成员变量，必须同步更新。size_t nodes_quantity_ = 0;// 链表为动态大小，因此要把数据放在堆区。std::unique_ptr<Node<T>> front_node_ptr_;// 移动到指定的节点位置，并且返回该节点。从 0 开始计算 node_index 。// node_index 可以是 0 ，也可以是最后一个 node 。Node<T>& goto_node(size_t node_index) { if (size() == 0) { // 处理空链表的情况。throw std::range_error("The forward list is empty!");}// 使用 get 返回的原始指针。因为原始指针只存活在这个函数内，生命周期极短，不会造成内存泄漏。check_index(node_index);Node<T>* running_node_ptr_ = front_node_ptr_.get();for (size_t i = 0; i < node_index; ++i) {// 获取下一个节点的原始指针。running_node_ptr_ = (running_node_ptr_->get_next_ptr()).get();}return *running_node_ptr_; // 只能返回堆区对象，不可返回原始指针，避免对象的生命周期管理混乱。}// 使用输入的数据，创建一个新的 node 。std::unique_ptr<Node<T>> create_node(const T& data){auto new_node_ptr{std::make_unique<Node<T>>()};new_node_ptr->set_data(data);++nodes_quantity_; return new_node_ptr; // 返回局部变量，编译器进行 NRVO 。}// 不允许索引大于节点数量。void check_index (const size_t node_index) const{ // 始终允许 node_index 为 0 ，无须判断节点数量。if ((node_index != 0) && (node_index >= nodes_quantity_)) {throw std::range_error("node_index + 1 > nodes_quantity_ \nnode_index= " + std::to_string(node_index) + " , nodes_quantity_= " + std::to_string(nodes_quantity_));}}
};
#endif // FORWARD_LIST_H_2. 使用示例
#include "forward_list.hpp"
#include <cctype>
#include <iostream>void insert_and_show() {ForwardList<int> foo;foo.push_front(2025);ForwardList<int> list{2025, 888};list.insert_before(0, 200);list.insert_before(0, 200);list.insert_after(3, 300); list.insert_after(3, 300); list.show_list();list.show_list();
}void delete_and_show() {ForwardList<int> list{100, 2025, 888, 2025};// list.delete_by_index(1);list.delete_by_index(0);list.show_list();list.delete_by_value(200);list.show_list();list.delete_by_value(2025);list.show_list();
}void copy_and_move() {ForwardList<int> list{2025, 888};ForwardList<int> foo;std::cout << "\nfoo = list\n";foo = list; // 调用拷贝赋值运算符。std::cout << "\nfoo.show_list()= ";foo.show_list();ForwardList<int> bar;std::cout << "\nbar = std::move(list)\n";bar = std::move(list); // 调用移动赋值运算符。std::cout << "\nbar.show_list()= ";bar.show_list();// 再查看原有链表。std::cout << "\nlist.show_list()= ";list.show_list();
}
void clear_and_show() {ForwardList<int> foo{2025, 888};std::cout << "\nfoo.show_list()= ";foo.show_list();foo.clear();std::cout << "\nfoo.show_list()= ";foo.show_list();
}int main() {insert_and_show();// delete_and_show(); // copy_and_move(); // clear_and_show(); return 0;
}调用 insert_and_show 的运行结果如下图：
—————————— 本文结束 ——————————