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.

Solution 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)

Solution 2

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

Solution 3

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

Solution 4

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.)

Solution 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.

View more solutions

Comments

[Admin]

@Mike Atlas: No just curiosity.

[Admin]

@Ken: They would defeat the purpose of the question.

[DVK]

Sorry, no code example as this smells like homework to me and I prefer not to answer h/w quesyions unless the poster is up-front about the fact.

[Admin]

you mean something like a std::vector<std::pair<T,std::size_t>> ?

[Billy ONeal]

@DVK: But then it's not a linked list.

[Billy ONeal]

But then it's not a linked list, it's a vector.

[Admin]

@DVK: True, then nor would your array be one either.

[Ben Voigt]

It's still a linked list, but it is also still using pointers. The term for this is "based pointer".

[Admin]

@Jeremy: As Billy mentioned, what you describe is not a linked-list wrt the true definition of the structure.

[Billy ONeal]

No you can't. The reference has to point to something that's allocated somewhere, and you can't have a linked list manage that memory like it can if you are using pointers. You'd still have to hold the allocated objects in your linked list somehow, and that wouldn't be a linked list.

[Matthew Flaschen]

It's not a vector or a linked list. It requires contiguous memory allocation, but it allows some linked list benefits (inserting and removing in anywhere in O(1)).

[luke]

@Billy ONeal i know, thats why it would be complicated. instead of a null pointer at the end you would create a special singleton instance for an empty list. the references would be set in constructors. if you look at Ken Blooms code this is pretty much what he is doing.

[Billy ONeal]

That's still not a linked list. Insertion or removal requires pushing up or down elements in your file. It's more like a vector data structure.

[Admin]

@Steven: Lets just assume the solution I'm looking for should not be based on anything other than standard OS memory allocation and code execution facilities.

[Richard Simões]

It is a linked list with all nodes occupying a continuous memory space. From Wikipedia: "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." What @Jeremy Friesner describes satisfies this definition.

[Ken Bloom]

Actually, you can avoid the issue with temporaries by giving each node a variable with a name, and making references to those. But that could also be living dangerously.

[Billy ONeal]

@Luke: You'd still have the problem of the fact that the thing the reference points at will die when you try to put it into the list. There's no way to ensure the references remain valid. If you look at Ken Bloom's code, note that none of the structure remains after a single statement.

[Admin]

@Ken: Your solution is no different than a static array, as the size of the structure has to be known at compile-time. Furthermore the size of the structure is entirely dependent on the compilers templating depth and not the amount of memory you have available.

[Steven Schlansker]

@Billy: I don't see how this is anything like a vector. If you want to insert between 1 and 5, you take 1 and change its reference to 6534, and then make 6534 point at 5. No "pushing" or "popping" needed.

[Steven Schlansker]

@sonicoder: Your question was weird enough that I felt compelled to be a little silly with it. Clearly this does not fit your desire to only use standard memory allocation, etc...

[Billy ONeal]

@Steven Schlansker: Because you had to put your new item into the array in order to update those references. You do get some of the benefits of a linked list (i.e. constant time insertion in the middle) with something like this, but the fact remains that the memory is being managed as a vector, not a list.

[Ken Bloom]

@sonicoder, this structure is not using nested templates, so the compiler's templating depth shouldn't affect anything. Moreover, if you used a recursive function to build the list and continuation passing style to operate on it then you could build a dynamically-sized list.

[Matthew Flaschen]

Nodes are in a vector (either a std::vector or otherwise), but it doesn't have the performance characteristics of std::vector<T>.

[Admin]

@Ken: Could you please demonstrate how one would insert a node between say, nodes 2 and 3?

[Ken Bloom]

@sonicoder: that can't be done. This is a cons-list, like one would find in a functional language, and those aren't intended to support insertions in the middle. (That's the only reason I can get away with this silly example. I if you want mutability you'll have to use pointers.)

[Richard Simões]

@Billy ONeal: A C++ array is a pointer to the first element of the array. An array index is an offset from this pointer. How is this not a reference (in a general computer science sense, not the C++ data type) when used as a reference?

[Ivan_Bereziuk]

Billy if an entry in the list has a link to the "previous" and "next" entry in hte list then it is a linked list. The original "linked List" implementations were database structures on disk which had logical pointers for "previous' and "next"

[luke]

@Billy ONeal my C++ is a little rusty, but couldn't you just construct the object on the heap and then create a reference from the pointer and then pass these 'new'd objects to the next constructor, this would extend the lifetime of the list objects. Now obviously it would be difficult to manage all these allocations.

[Jeremy Friesner]

It seems a bit silly to quibble about definitions, but I'd call it a linked list with an extremely simple custom node-allocator algorithm. @Billy, I think you are incorrect about the liabilities; this can be implemented without requiring the invalidation of iterators, and the reallocation of the entire underlying array is avoided simply by having the insertion fail if the array is full.

[Steven Schlansker]

What is main memory but a very, very large array, then? :-p

[deft_code]

@billy: by your logic a std::map using a pooled allocator would also be a vector if the pool use contiguous memory.

[luke]

yeah but not in the datastructure itself

[SigTerm]

@Billy ONeal: Give up already. Pointer is technically index, and index is technically pointer. If a list is stored in array AND uses indicies for parent/child, it is still a list. AND searching for a free element in such list can be easily optimized down to O(n) operation - at the cost of sizeof(int)*maximumSize of memory.

[Jeremy Friesner]

@Billy: Yes, I am making that tradeoff, but I said that up front in the original answer. I think the result is still a linked list in the ways that count (O(1) insertion/removal, O(N) lookup time, previous/next links, immutable/persistent node addresses)

[Ramónster]

the link doesn't have to be an absolute memory address, it can be relative to a pointer, aka an array index. See the other answers.

[Billy ONeal]

@Ramónster: I have responded to the other answers with why I believe them incorrect.

[dmckee --- ex-moderator kitten]

"Okay, so you've traded consistency for extremely limited use of space. It's still does not have the semantics of a list" No. Though we have grown used to the idea that a "link list" has access to the whole address space provided by the chip, that has historically not been the case. If you insist on it, you are claiming that no one ever implemented a "linked list" on the classic Mac OSs. Pure nonsense. Limited allocators are less useful than a machine native lists residing in a fully virtualized heap (which is still not arbitrarily extensible), but they are still linked lists.

[Joshua Hartman]

Unfortunately, you can't really use this list since you're storing references to data allocated on the stack. If the list is returned from a function, the references will no longer be valid.