我的问题很简单，可以使用 C++ 实现链接列表数据结构而不使用指针(下一个节点)吗？为了进一步限定我的问题，我的意思是可以仅使用类实例化来创建链接列表数据结构。
一个常见的节点定义可能是这样的:
template<typename T>
struct node
{
T t;
node<T>* next;
node<T>* prev;
};
我知道 std::list 等，我只是想知道它是否可能 - 如果是的话怎么做？代码示例将不胜感激。
更多说明:
- 插入次数应为 O(1)。
- 遍历不应超过 O(n)。
- 真实节点和空节点应该是可区分的。
- 链表的大小应仅受可用内存量的限制。
最佳答案
当然，如果您不介意链表具有最大大小，您可以静态分配列表节点数组，然后使用数组中的整数索引作为每个节点的“上一个”和“下一个”值，而不是指针。我过去这样做是为了节省一点内存(因为整数可以是 2 或 4 字节，而在 64 位系统上，指针将是 8 字节)
关于c++ - 不使用指针的链表实现是否可行？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3002764/