Using C++ is a Linked-List implementation without using pointers possible or not?

Question

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.

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

Can one using C++, implment a link-list data structure without using pointers (next nodes)?
No.

Answer 2

Yes, it's possible. Use array indexes instead of pointers.

Answer 3

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)

Answer 4

You could make a linked-list using references, but that would probably be more complicated than necessary. you would have to implement an immutable linked-list which would be complicated without a built in garbage collector.

Answer 5

One could create a list of cons-cells using temporaries, const references, and inheritance. But you'd have to be very careful not to keep any references to it beyond its lifetime. And you probably couldn't get away with anything mutable.

This is based roughly on the Scala implementation of these lists (in particular the idea of using inheritance and a NilList subclass rather than using null pointers).

template<class T>
struct ConsList{
   virtual T const & car() const=0;
   virtual ConsList<T> const & cdr() const=0;
}

template<class T>
struct ConsCell:ConsList{
   ConsCell(T const & data_, ConsList<T> const & next_):
        data(data_),next(next_){}
   virtual T const & car() const{return data;}
   virtual ConstList<T> const & cdr() const{return next;}

   private:
     T data;
     ConsList<T> const & next;
}

template<class T>
struct NilList:ConsList{  
   // replace std::exception with some other kind of exception class
   virtual T const & car() const{throw std::exception;}
   virtual ConstList<T> const & cdr() const{throw std::exception;}
}

void foo(ConsList<int> const & l){
   if(l != NilList<int>()){
      //...
      foo(NilList.cdr());
   }
}

foo(ConsList<int>(1,ConsList(2,ConsList<int>(3,NilList<int>()))));
// the whole list is destructed here, so you better not have
// any references to it stored away when you reach this comment.

Answer 6

While I'm not sure just what the context behind your question is, if you do a little out of the box thinking I'm sure you can.

DVK suggested arrays, which is quite true, but arrays are simply thin wrappers around pointer arithmetic.

How about something entirely different: use the filesystem to do the storage for you!

for example, the file /linked-list/1 contains the data:

Data 1!

5

and /linked-list/5 is the next node in the list...

If you're willing to hack enough, anything is possible :-p

Note that said implementation's complexity / speed is entirely dependent on your filesystem (i.e. it's not necessarily O(1) for everything)

Answer 7

From Wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

Nothing in that definition specifies the manner in which the reference is stored or used. If you don't store a reference, it isn't a linked list -- it's something else.

If your goal is merely to avoid using a pointer (or object reference), then using a vector with an index is a common implementation. (One of the reasons for using the vector/index implementation is persistence: it's really hard to correctly persist pointers / object references outside of the active memory space.)

Answer 8

I suppose using references is cheating and, technically, this causes UB, but here you go:

// Beware, un-compiled code ahead!
template< typename T >
struct node;

template< typename T >
struct links {
  node<T>& prev;
  node<T>& next;
  link(node<T>* prv, node<T>* nxt); // omitted
};

template< typename T >
struct node {
  T data;
  links<T> linked_nodes;
  node(const T& d, node* prv, node* nxt); // omitted
};

// technically, this causes UB...
template< typename T >
void my_list<T>::link_nodes(node<T>* prev, node<T>* next)
{
  node<T>* prev_prev = prev.linked_nodes.prev;
  node<T>* next_next = next.linked_nodes.next;
  prev.linked_nodes.~links<T>();
  new (prev.linked_nodes) links<T>(prev_prev, next);
  next.linked_nodes.~links<T>();
  new (next.linked_nodes) links<T>(next, next_next);
}

template< typename T >
void my_list<T>::insert(node<T>* at, const T& data)
{
  node<T>* prev = at;
  node<T>* next = at.linked_nodes.next;
  node<T>* new_node = new node<T>(data, prev, next);

  link_nodes(prev, new_node);
  link_nodes(new_node, next);
}

Answer 9

Yes:

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

Inspired by a comment about the origins of linked lists

Answer 10

Wow, NO? Surely you guys are not serious?

All a linked list needs is a link. Nothing says it has to be a pointer. Consider the case of wanting to store a linked list in shared mem, where the base addr is dynamic? Answer is simply, store the link as a Offset from the start of the mem block, (or some other constant) and redefine the iterator to do the actual logic of adding the base addr. Obviously, insert etc would have to be changed as well.

But fairly trivial!

Allan