c++ - C++ 中的链表使用引用而不是指针

Question

假设我想创建一个不可修改的链表(即它只能被遍历，一旦最初创建就不能添加或删除任何节点)。这可以通过以下方式轻松实现:

struct ListNode
{
  int value;
  ListNode* nextNode;
}

我的问题是......是否可以使用引用而不是指针？

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

我不确定它是否会带来任何性能提升，但是......这个问题在编码时突然出现，目前我的回答是否，但我可能会遗漏一些东西。

原则上，没有什么能阻止您像这样使用引用和构造列表元素:

ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

但是存在先有鸡还是先有蛋的问题，因为 next 还强制其 next 元素在其创建时存在，依此类推...

注意:我认为我的问题也可以应用于将列表定义为:

struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}

Answer 1

这是函数式语言中典型的cons-list:

data List a = Empty | Node a (List a)

技巧是，List a是完整类型，可以引用任一个 Empty或者另一个节点(这就是它可以终止的原因)。

为了在 C++ 中实现这一点，您可以利用 union (但它没有得到很好的支持)或多态性。

template <typename T>
struct ListBase {
    enum class Kind { Empty, Node };
    explicit ListBase(Kind k): _kind(k) {}

    Kind _kind;
};

然后:

template <typename T>
struct EmptyList: ListBase<T> {
    EmptyList(): ListBase<T>(Kind::Empty) {}
};

template <typename T>
struct ListNode: ListBase<T> {
    ListNode(T const& t, ListBase<T>& next):
        ListBase<T>(Kind::Node), _value(t), _next(next) {}

    T _value;
    ListBase<T>& _next;
};

现在，您不再有先有鸡还是先有蛋的问题；只需从 EmptyList<T> 的实例化开始.

注意:_kind 的存在基类中的不是那个 OO，但它通过标记使用的替代方案使事情更接近功能示例。