是不使用指针的链表的实现吗？ [英] Is a Linked-List implementation without using pointers possible or not?

问题描述

我的问题很简单，可以使用C ++，隐含一个链接列表数据结构，而不使用指针（下一个节点）？为了进一步限定我的问题，我的意思是可以只使用类实例化创建一个链接列表数据结构。

My question is very simple, can one using C++, implment 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.

一个公共节点定义可能是这样： p>

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. 链接列表的大小只应受可用内存量的限制。

1. Insertions should be O(1)
2. Traversal should be no more than O(n)
3. A real node and a null node should be differentiable
4. The size of the linked-list should only be limited by the amount of memory available.

推荐答案

当然，如果你不介意链表具有最大大小，你可以静态分配一个列表节点数组，然后使用整数索引作为你的previous和next 值为每个节点，而不是指针。我在过去这样做是为了节省一点内存（因为一个整数可以是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)

这篇关于是不使用指针的链表的实现吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！