不使用指针的链表实现是否可行?

2021-12-13 00:00:00 linked-list pointers c++

我的问题很简单，是否可以使用 C++，在不使用指针(下一个节点)的情况下实现链表数据结构?为了进一步限定我的问题，我的意思是可以仅使用类实例化来创建链表数据结构.

My question is very simple, can one using C++, implement a link-list data structure without using pointers (next nodes)? To further qualify my question, I'm mean can one create a Linked-List data structure using only class instantiations.

一个常见的节点定义可能是这样的:

A common node definition might be like so:

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

我知道 std::list 等，我只是想知道它是否可能 - 如果有的话如何?代码示例将不胜感激.

I'm aware of std::list etc, I'm just curious to know if its possible or not - and if so how? Code examples will be greatly appreciated.

更多说明:

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

推荐答案

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

Sure, if you don't mind the linked list having a maximum size, you could statically allocate an array of list nodes, and then use integer indices into the array as your "previous" and "next" values for each node, rather than pointers. I've done in this in the past to save a bit of memory (since an integer can be either 2 or 4 bytes, whereas on a 64-bit system a pointer will be 8 bytes)

相关文章