使用 LinkedList class 指向 head Node 与仅使用 Node* 的内在好处
Intrinsic benefit of using a LinkedList class to point to head Node vs. just using Node*
我们可以定义一个LinkedListNode如下：
template <typename T>
struct LinkedListNode {
T val;
LinkedListNode* next;
LinkedListNode() : val{}, next(nullptr) {}
LinkedListNode(T x) : val{ x }, next(nullptr) {}
LinkedListNode(T x, LinkedListNode* next) : val{ x }, next(next) {}
};
如果我们想定义一个接受“链表”的函数，我们有两个选择。首先，我们可以将 LinkedListNode* 传递给函数。
template <typename T>
int func(LinkedListNode<T>* node);
其次，我们可以定义一个 LinkedList class 来保存指向“头”节点的指针。然后我们可以定义一个接受 LinkedList.
的函数
template <typename T>
struct LinkedList {
LinkedListNode<T>* head;
// other member functions
};
template <typename T>
int func(LinkedList<T>& llist);
第二种看起来更可取的一个原因是它可能允许更好地封装修改“链表”的函数。例如，采用 LinkedListNode* 的 FindMax 可能更适合作为 LinkedList 的成员函数而不是 LinkedListNode.
的成员函数
有哪些具体原因使您更喜欢其中一个？我对您可能更喜欢只使用 LinkedListNode* 的原因特别感兴趣。
定义一个实际的 LinkedList 类型允许您直接支持那些通过传递指向节点的指针相对难以支持的操作。
有评论已经提到将链表的大小存储为成员，所以你可以有一个函数return常数时间内链表的大小。这是一件有用的事情，但我认为它只是暗示了真正的要点，即（在我看来）将东西应用于整个链表，而不仅仅是对单个节点的操作。
在 C++ 中，一个明显的可能性是有一个析构函数，当它超出范围时可以正确地销毁完整的链表。
int foo() {
LinkedList a;
// code that uses `a`
} // <-- here `a` goes out of scope, and should be destroyed
作为一个整体，C++ 的一大特点是确定性析构，它对此的支持基于当对象超出范围时 运行 的析构函数。
使用链表，您（至少通常）计划动态分配链表中的所有节点。如果你只是使用一个指向节点的指针，当你不再need/want一个特定的链表时，由你来跟踪，并在不再需要时手动销毁链表中的所有节点。
通过创建链表 [=30=]，您可以获得确定性破坏的好处，因此您不再需要跟踪何时不再需要列表 - 编译器会为您跟踪，当它超出范围时，它会自动销毁。
我还希望链表支持复制构造、移动构造、复制赋值和移动赋值——可能还有一些类似比较的东西（至少 in/equality，可能还有排序).如果您决定将链表实现为指向节点的指针，而不是拥有实际的链表，那么所有这些都需要大量的手动干预 class.
因此，我想说如果您真的想使用 C++（甚至接近它的预期工作方式）创建一个 class 来封装您的链表是绝对必要的。只要您只是传递指向节点的指针，您所编写的基本上就是 C 代码（即使它可能使用某些特定于 C++ 的功能，因此 C 编译器不会接受它）。
我认为在你甚至选择使用单个 linked 列表之前，你应该有一些理由使用它而不是普通的 std::vector。您需要实际的基准测试来表明单个 linked 列表可以提高您所考虑的特定应用程序的性能；你会惊讶于它经常让事情变得更糟，而不是更好。提示：理论上的计算复杂度与内存访问模式是正交的，在现代 CPU 上，内存访问模式决定了性能——大多数计算基本上是免费的，因为它不需要额外的时间：它隐藏在所有缓存未命中的情况下。
那你应该有理由不使用std::forward_list。但也许您需要侵入式 linked 列表：然后说明不使用 boost::intrusive::slist<T> 或类似的现有且经过良好测试的库类型。
如果您仍在继续自己的实现，那么第一步就是使用 std::unique_ptr 作为 child 节点的拥有指针，而不是手动内存管理 - 即很容易证明没有内存泄漏 - 代码通过构造变得正确，内存泄漏需要额外的努力而不是通过遗漏发生。
换句话说：除非您有明确的理由，否则不要重新发明轮子。当然，您可以将 linked 列表作为练习来实现，但请注意，您最有可能实现的是一个您使用最少的容器 - 所以我认为您d 通过实现例如，更多地了解 C++ 的工作原理一个 vector/array 容器。
如果您确实使用 std::unique_ptr，甚至手动内存管理，您很可能 运行 陷入析构函数堆栈爆炸的陷阱。考虑
template <typename T>
struct LinkedListNode1 {
T val;
std::unique_ptr<LinkedListNode1> next;
};
template <typename T>
struct LinkedListNode2 {
T val;
LinkedListNode2* next = nullptr;
~LinkedListNode2() { delete next; }
};
在这两种情况下，析构函数都会被递归调用，如果列表足够长，您将 运行 出栈。递归通常也比循环效率低。为防止这种情况，您绝不能取消分配具有 non-null next.
的节点
template <typename T>
struct LinkedListNode1 {
T val;
std::unique_ptr<LinkedListNode1> next;
~LinkedListNode1() {
auto node = std::move(next);
while (node)
node = std::move(node->next);
assert(!next);
}
};
template <typename T>
struct LinkedListNode2 {
T val;
LinkedListNode2* next = {};
~LinkedListNode2() {
using std::swap;
LinkedListNode2* node = {};
swap(node, next);
while (node) {
LinkedListNode2* tmp = {};
swap(tmp, node);
assert(!node);
swap(node, tmp->next);
assert(!tmp->next);
delete tmp;
}
assert(!next);
}
};
智能指针让代码更简单。我写了带有交换的原始指针版本，以便更容易地表明没有内存泄漏：正确使用的交换永远不会“丢失”一个值。
For example, a FindMax that takes a LinkedListNode*
这又是在重新发明轮子。在 C++ 中，“查找最大元素”的成语是 std::max_element from #include <algorithm>。您应该利用标准库提供的算法（以及您可能需要的任何其他算法，例如来自 Boost 或 header-only 库）。
为此，您需要一个列表迭代器。它将必然是一个 LegacyForwardIterator。在这里，is a 具有严格的技术含义：它是一种简洁的表达方式，“您的迭代器将履行 LegacyForwardIterator[=90= 的概念并遵守其约定]".
这样的迭代器大致如下所示：
template <typename T>
class LinkedListNode1 {
std::unique_ptr<LinkedListNode1> next;
template <typename V> class iterator_impl {
LinkedListNode1 *node = {};
using const_value_type = std::add_const_t<V>;
using non_const_value_type = std::remove_const_t<V>;
public:
using value_type = V;
using reference = V&;
using pointer = V*;
iterator_impl() = default;
template <typename VO>
iterator_impl(const iterator_impl<VO> &o) : node(o.operator->()) {}
explicit iterator_impl(LinkedListNode1 *node) : node(node) {}
auto *operator->() const { return node; }
pointer operator&() const { return &(node->val); }
reference operator*() const { return node->val; }
iterator_impl &operator++() { node = node->next.get(); return *this; }
iterator_impl operator++(int) {
auto retval = *this;
this->operator++();
return retval;
}
bool operator==(const iterator_impl &o) const { return node == o.node; }
bool operator!=(const iterator_impl &o) const { return node != o.node; }
};
public:
T val;
using iterator = iterator_impl<T>;
using const_iterator = iterator_impl<const T>;
next 指针可以设为私有。然后，基本功能将包括：
LinkedListNode1() = default;
LinkedListNode1(const T &val) : val(val) {}
~LinkedListNode1() {
auto node = std::move(next);
while (node)
node = std::move(node->next);
}
iterator begin() { return iterator(this); }
iterator end() { return {}; }
const_iterator begin() const { return const_iterator(this); }
const_iterator end() const { return {}; }
const_iterator cbegin() const { return const_iterator(this); }
const_iterator cend() const { return {}; }
iterator insert_after(const_iterator pos, const T& value) {
auto next = std::make_unique<LinkedListNode1>();
next->val = value;
auto retval = iterator(next.get());
pos->next = std::move(next);
return retval;
}
人们会使用 insert_after 来扩展列表。当然，还需要添加其他此类方法。
然后，我们可能还想支持初始化列表：
LinkedListNode1(std::initializer_list<T> init) {
auto src = init.begin();
if (src == init.end()) return;
val = *src++;
for (auto dst = iterator(this); src != init.end(); ++src)
dst = insert_after(dst, *src);
}
};
现在您可以 pre-populate 带有初始化列表的列表，使用 range-for 对其进行迭代，并将其与标准算法一起使用：
#include <iostream>
int main() {
LinkedListNode1<int> list{1, 3, 2};
for (auto const &val : list)
std::cout << val << '\n';
assert(*std::max_element(list.begin(), list.end()) == 3);
}
但现在我们来到最重要的问题：
What concrete reasons are there to prefer one over the other
默认 - 起点 - 是提供一个容器，因为这是我们处理的抽象：你想到的“东西”是linked list，不是 list 节点。您学习的数据结构同样是 linked list。并且有一个很好的理由：节点类型是一个实现细节，因此您需要想出 application-specific 公开节点类型的理由，并且在面对迭代器时所做的任何论点都必须经得起审查。您 真的 需要公开那些节点，还是您真正想要的只是一种方便的方法来迭代存储在 collection 中的项目，或者拆分列表等？其中任何一个都不需要节点访问。这都是一个已解决的问题，您将通过阅读 std::forward_list.
的文档了解这一点
您还需要考虑分配器支持。我不担心 C++98 分配器，但多态分配器（终于！）实际上可用了，所以你想实现那些（c.f。std::pmr::polymorphic_allocator 和 std::pmr 一般命名空间）。
要获得全部功能，您几乎需要添加大多数 std::forward_list 的方法和构造函数。所以它需要做一些工作，并且有很多细节可以使它无论值类型如何都能正常工作。因此我们又回到了原点：真正的容器是有用的而不用担心 low-level 细节是很多工作，但它们使用起来很愉快 - 它们看起来不像大多数教科书“教学”代码。
A linked 列表经常在教授数据结构时使用 - 是的。然而，大多数用于教学的 C++ 书籍在演示方面严重不足g 一个现代的、功能齐全的数据 structure/container 需要什么——他们甚至不能正确处理像单个 linked 列表这样“简单”的东西。
C-like 单 linked 列表 - 正是你在问题中开始的内容 - 和单 linked 列表 C++ 容器之间的差距大约是几千行代码和测试。这是他们通常不教的内容，而这正是最重要的部分：它们是玩具代码和生产代码之间的区别。
即使没有测试，一个功能齐全的单一 linked 列表容器在没有多态分配器支持的情况下也有大约 500 行，并且可能至少是有这种支持的两倍，并且测试会使代码大小加倍数倍 -尽管如果您对此很聪明，您可以重用各种 STL 实现所使用的大量测试:)
而且，顺便说一句：在 C 中 linked 列表的良好实现不会强迫您手动处理节点 或者 。列表本身 - 容器 - 将是一个抽象数据类型，具有一堆提供功能的函数，以及对迭代器的一些抽象（即使它们只是一些 type-safe 伪装的指针）。这又是教学代码与 easy-to-use-correctly 和 hard-to-use-incorrectly 生产代码之间的区别。我现在能想到的一个例子是在 Bitwise ion 项目中实现的弹性缓冲区。这是一个 link 的视频，其中这些是实时实现的，它们是抽象如何在 C 中工作的一个很好的例子（以及你绝对不应该用 C++ 编写它的方式 - C 和 C++ 是不同的语言！）。
我们可以定义一个LinkedListNode如下：
template <typename T>
struct LinkedListNode {
T val;
LinkedListNode* next;
LinkedListNode() : val{}, next(nullptr) {}
LinkedListNode(T x) : val{ x }, next(nullptr) {}
LinkedListNode(T x, LinkedListNode* next) : val{ x }, next(next) {}
};
如果我们想定义一个接受“链表”的函数，我们有两个选择。首先，我们可以将 LinkedListNode* 传递给函数。
template <typename T>
int func(LinkedListNode<T>* node);
其次，我们可以定义一个 LinkedList class 来保存指向“头”节点的指针。然后我们可以定义一个接受 LinkedList.
template <typename T>
struct LinkedList {
LinkedListNode<T>* head;
// other member functions
};
template <typename T>
int func(LinkedList<T>& llist);
第二种看起来更可取的一个原因是它可能允许更好地封装修改“链表”的函数。例如，采用 LinkedListNode* 的 FindMax 可能更适合作为 LinkedList 的成员函数而不是 LinkedListNode.
有哪些具体原因使您更喜欢其中一个？我对您可能更喜欢只使用 LinkedListNode* 的原因特别感兴趣。
定义一个实际的 LinkedList 类型允许您直接支持那些通过传递指向节点的指针相对难以支持的操作。
有评论已经提到将链表的大小存储为成员，所以你可以有一个函数return常数时间内链表的大小。这是一件有用的事情，但我认为它只是暗示了真正的要点，即（在我看来）将东西应用于整个链表，而不仅仅是对单个节点的操作。
在 C++ 中，一个明显的可能性是有一个析构函数，当它超出范围时可以正确地销毁完整的链表。
int foo() {
LinkedList a;
// code that uses `a`
} // <-- here `a` goes out of scope, and should be destroyed
作为一个整体，C++ 的一大特点是确定性析构，它对此的支持基于当对象超出范围时 运行 的析构函数。
使用链表，您（至少通常）计划动态分配链表中的所有节点。如果你只是使用一个指向节点的指针，当你不再need/want一个特定的链表时，由你来跟踪，并在不再需要时手动销毁链表中的所有节点。
通过创建链表 [=30=]，您可以获得确定性破坏的好处，因此您不再需要跟踪何时不再需要列表 - 编译器会为您跟踪，当它超出范围时，它会自动销毁。
我还希望链表支持复制构造、移动构造、复制赋值和移动赋值——可能还有一些类似比较的东西（至少 in/equality，可能还有排序).如果您决定将链表实现为指向节点的指针，而不是拥有实际的链表，那么所有这些都需要大量的手动干预 class.
因此，我想说如果您真的想使用 C++（甚至接近它的预期工作方式）创建一个 class 来封装您的链表是绝对必要的。只要您只是传递指向节点的指针，您所编写的基本上就是 C 代码（即使它可能使用某些特定于 C++ 的功能，因此 C 编译器不会接受它）。
我认为在你甚至选择使用单个 linked 列表之前，你应该有一些理由使用它而不是普通的 std::vector。您需要实际的基准测试来表明单个 linked 列表可以提高您所考虑的特定应用程序的性能；你会惊讶于它经常让事情变得更糟，而不是更好。提示：理论上的计算复杂度与内存访问模式是正交的，在现代 CPU 上，内存访问模式决定了性能——大多数计算基本上是免费的，因为它不需要额外的时间：它隐藏在所有缓存未命中的情况下。
那你应该有理由不使用std::forward_list。但也许您需要侵入式 linked 列表：然后说明不使用 boost::intrusive::slist<T> 或类似的现有且经过良好测试的库类型。
如果您仍在继续自己的实现，那么第一步就是使用 std::unique_ptr 作为 child 节点的拥有指针，而不是手动内存管理 - 即很容易证明没有内存泄漏 - 代码通过构造变得正确，内存泄漏需要额外的努力而不是通过遗漏发生。
换句话说：除非您有明确的理由，否则不要重新发明轮子。当然，您可以将 linked 列表作为练习来实现，但请注意，您最有可能实现的是一个您使用最少的容器 - 所以我认为您d 通过实现例如，更多地了解 C++ 的工作原理一个 vector/array 容器。
如果您确实使用 std::unique_ptr，甚至手动内存管理，您很可能 运行 陷入析构函数堆栈爆炸的陷阱。考虑
template <typename T>
struct LinkedListNode1 {
T val;
std::unique_ptr<LinkedListNode1> next;
};
template <typename T>
struct LinkedListNode2 {
T val;
LinkedListNode2* next = nullptr;
~LinkedListNode2() { delete next; }
};
在这两种情况下，析构函数都会被递归调用，如果列表足够长，您将 运行 出栈。递归通常也比循环效率低。为防止这种情况，您绝不能取消分配具有 non-null next.
template <typename T>
struct LinkedListNode1 {
T val;
std::unique_ptr<LinkedListNode1> next;
~LinkedListNode1() {
auto node = std::move(next);
while (node)
node = std::move(node->next);
assert(!next);
}
};
template <typename T>
struct LinkedListNode2 {
T val;
LinkedListNode2* next = {};
~LinkedListNode2() {
using std::swap;
LinkedListNode2* node = {};
swap(node, next);
while (node) {
LinkedListNode2* tmp = {};
swap(tmp, node);
assert(!node);
swap(node, tmp->next);
assert(!tmp->next);
delete tmp;
}
assert(!next);
}
};
智能指针让代码更简单。我写了带有交换的原始指针版本，以便更容易地表明没有内存泄漏：正确使用的交换永远不会“丢失”一个值。
For example, a
FindMaxthat takes aLinkedListNode*
这又是在重新发明轮子。在 C++ 中，“查找最大元素”的成语是 std::max_element from #include <algorithm>。您应该利用标准库提供的算法（以及您可能需要的任何其他算法，例如来自 Boost 或 header-only 库）。
为此，您需要一个列表迭代器。它将必然是一个 LegacyForwardIterator。在这里，is a 具有严格的技术含义：它是一种简洁的表达方式，“您的迭代器将履行 LegacyForwardIterator[=90= 的概念并遵守其约定]".
这样的迭代器大致如下所示：
template <typename T>
class LinkedListNode1 {
std::unique_ptr<LinkedListNode1> next;
template <typename V> class iterator_impl {
LinkedListNode1 *node = {};
using const_value_type = std::add_const_t<V>;
using non_const_value_type = std::remove_const_t<V>;
public:
using value_type = V;
using reference = V&;
using pointer = V*;
iterator_impl() = default;
template <typename VO>
iterator_impl(const iterator_impl<VO> &o) : node(o.operator->()) {}
explicit iterator_impl(LinkedListNode1 *node) : node(node) {}
auto *operator->() const { return node; }
pointer operator&() const { return &(node->val); }
reference operator*() const { return node->val; }
iterator_impl &operator++() { node = node->next.get(); return *this; }
iterator_impl operator++(int) {
auto retval = *this;
this->operator++();
return retval;
}
bool operator==(const iterator_impl &o) const { return node == o.node; }
bool operator!=(const iterator_impl &o) const { return node != o.node; }
};
public:
T val;
using iterator = iterator_impl<T>;
using const_iterator = iterator_impl<const T>;
next 指针可以设为私有。然后，基本功能将包括：
LinkedListNode1() = default;
LinkedListNode1(const T &val) : val(val) {}
~LinkedListNode1() {
auto node = std::move(next);
while (node)
node = std::move(node->next);
}
iterator begin() { return iterator(this); }
iterator end() { return {}; }
const_iterator begin() const { return const_iterator(this); }
const_iterator end() const { return {}; }
const_iterator cbegin() const { return const_iterator(this); }
const_iterator cend() const { return {}; }
iterator insert_after(const_iterator pos, const T& value) {
auto next = std::make_unique<LinkedListNode1>();
next->val = value;
auto retval = iterator(next.get());
pos->next = std::move(next);
return retval;
}
人们会使用 insert_after 来扩展列表。当然，还需要添加其他此类方法。
然后，我们可能还想支持初始化列表：
LinkedListNode1(std::initializer_list<T> init) {
auto src = init.begin();
if (src == init.end()) return;
val = *src++;
for (auto dst = iterator(this); src != init.end(); ++src)
dst = insert_after(dst, *src);
}
};
现在您可以 pre-populate 带有初始化列表的列表，使用 range-for 对其进行迭代，并将其与标准算法一起使用：
#include <iostream>
int main() {
LinkedListNode1<int> list{1, 3, 2};
for (auto const &val : list)
std::cout << val << '\n';
assert(*std::max_element(list.begin(), list.end()) == 3);
}
但现在我们来到最重要的问题：
What concrete reasons are there to prefer one over the other
默认 - 起点 - 是提供一个容器，因为这是我们处理的抽象：你想到的“东西”是linked list，不是 list 节点。您学习的数据结构同样是 linked list。并且有一个很好的理由：节点类型是一个实现细节，因此您需要想出 application-specific 公开节点类型的理由，并且在面对迭代器时所做的任何论点都必须经得起审查。您 真的 需要公开那些节点，还是您真正想要的只是一种方便的方法来迭代存储在 collection 中的项目，或者拆分列表等？其中任何一个都不需要节点访问。这都是一个已解决的问题，您将通过阅读 std::forward_list.
您还需要考虑分配器支持。我不担心 C++98 分配器，但多态分配器（终于！）实际上可用了，所以你想实现那些（c.f。std::pmr::polymorphic_allocator 和 std::pmr 一般命名空间）。
要获得全部功能，您几乎需要添加大多数 std::forward_list 的方法和构造函数。所以它需要做一些工作，并且有很多细节可以使它无论值类型如何都能正常工作。因此我们又回到了原点：真正的容器是有用的而不用担心 low-level 细节是很多工作，但它们使用起来很愉快 - 它们看起来不像大多数教科书“教学”代码。
A linked 列表经常在教授数据结构时使用 - 是的。然而，大多数用于教学的 C++ 书籍在演示方面严重不足g 一个现代的、功能齐全的数据 structure/container 需要什么——他们甚至不能正确处理像单个 linked 列表这样“简单”的东西。
C-like 单 linked 列表 - 正是你在问题中开始的内容 - 和单 linked 列表 C++ 容器之间的差距大约是几千行代码和测试。这是他们通常不教的内容，而这正是最重要的部分：它们是玩具代码和生产代码之间的区别。
即使没有测试，一个功能齐全的单一 linked 列表容器在没有多态分配器支持的情况下也有大约 500 行，并且可能至少是有这种支持的两倍，并且测试会使代码大小加倍数倍 -尽管如果您对此很聪明，您可以重用各种 STL 实现所使用的大量测试:)
而且，顺便说一句：在 C 中 linked 列表的良好实现不会强迫您手动处理节点 或者 。列表本身 - 容器 - 将是一个抽象数据类型，具有一堆提供功能的函数，以及对迭代器的一些抽象（即使它们只是一些 type-safe 伪装的指针）。这又是教学代码与 easy-to-use-correctly 和 hard-to-use-incorrectly 生产代码之间的区别。我现在能想到的一个例子是在 Bitwise ion 项目中实现的弹性缓冲区。这是一个 link 的视频，其中这些是实时实现的，它们是抽象如何在 C 中工作的一个很好的例子（以及你绝对不应该用 C++ 编写它的方式 - C 和 C++ 是不同的语言！）。