是否可以使用指针链接列表实现？

Question

我的问题很简单,可以使用C++,实现链接列表数据结构而不使用指针(下一个节点)吗？为了进一步限定我的问题,我的意思是可以只使用类实例创建一个Linked-List数据结构.

常见的节点定义可能如下:

template<typename T>
struct node
{
   T t;
   node<T>* next;
   node<T>* prev;
};

我知道std::list等等,我只是想知道它是否可能 - 如果是这样的话怎么样？代码示例将不胜感激.

更多说明:

1. 插入应为O(1).
2. 遍历不应超过O(n).
3. 真实节点和空节点应该是可区分的.
4. 链表的大小应仅受可用内存量的限制.

Answer 1

当然,如果您不介意链接列表具有最大大小,您可以静态分配列表节点数组,然后使用整数索引作为每个节点的"上一个"和"下一个"值,而不是指针.我在过去做过这个以节省一点内存(因为整数可以是2或4个字节,而在64位系统上,指针将是8个字节)

Answer 2

是的,这是可能的.使用数组索引而不是指针.

Answer 3

来自维基百科:

在计算机科学中,链表是由一系列数据记录组成的数据结构,使得在每个记录中存在包含到序列中的下一记录的引用(即,链接)的字段.

该定义中没有任何内容指定存储或使用引用的方式.如果您不存储引用,则它不是链接列表 - 它是其他内容.

如果您的目标仅仅是避免使用指针(或对象引用),那么使用带索引的向量是一种常见的实现方式.(使用向量/索引实现的原因之一是持久性:在活动内存空间之外正确地持久保存指针/对象引用非常困难.)

Answer 4

是:

class node { 
  std::string filenameOfNextNode;
  std::string filenameOfPrevNode;
  std::string data;
  node nextNode() {
    node retVal;
    std::ifstream file(filenameOfNextNode.c_str());
    retVal.filenameOfNextNode = file.getline();
    retVal.filenameOfPrevNode = file.getline();
    retVal.data = file.getline();
    return retVal;
  }
};

受到关于链表起源的评论的启发

Answer 5

使用 C++ 可以在不使用指针（下一个节点）的情况下实现链接列表数据结构吗？
不。