c++ - Is a Linked-List implementation without using pointers possible or not?

Question

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;
};

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.

More clarifications:

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.

Answer 1

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)