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)

Answer 2

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

Answer 3

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 4

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

Yes you can, it is not necessary to use pointers for a link list. It is possible to link a list without using pointers. You can statically allocate an array for the nodes, and instead of using next and previous pointer, you can just use indexes. You can do that to save some memory, if your link list is not greater than 255 for example, you can use 'unsigned char' as index (referencing C), and save 6 bytes for next and previous indications.

You may need this kind of array in embedded programming, since memory limitations can be troublesome sometimes.

Also keep in mind that your link list nodes will not necessary be contiguous in the memory.

Let's say your link list will have 60000 nodes. Allocating a free node from the array using a linear search should be inefficient. Instead, you can just keep the next free node index everytime:

Just initialize your array as each next index shows the current array index + 1, and firstEmptyIndex = 0.

When allocating a free node from the array, grab the firstEmptyIndex node, update the firstEmptyIndex as next index of the current array index (do not forget to update the next index as Null or empty or whatever after this).

When deallocating, update the next index of the deallocating node as firstEmptyIndex, then do firstEmptyIndex = deallocating node index.

In this way you create yourself a shortcut for allocating free nodes from the array.

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

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 10

Languages that do not support any type of reference can still create links by replacing pointers with array indices. The approach is to keep an array of records, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Not all nodes in the array need be used. If records are also not supported, parallel arrays can often be used instead.

As an example, consider the following linked list record that uses arrays instead of pointers:

record Entry {
integer next; // index of next entry in array
string data; // can be anything a struct also. }

Creata an array with a high number. And point listHead to the first indice element at the array

integer listHead;
Entry Records[10000];

Check wiki page: http://en.wikipedia.org/wiki/Linked_list for details, search for "Linked lists using arrays of nodes"

Answer 11

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

Answer 12

A possible approach would be to use an array of Nodes where each node stores an (array) index to the prev and next Node. Thus, your Node would look something like:

struct Node 
{
    T data;
    int prev;    // index of the previous Node of the list
    int next;    // index of the next Node of the list
}

Additionally, you will probably have to dynamically allocate the Node array, implement some bookkeeping to get and free space in the array: for example a bool array that stores the unoccupied indexes in the Node array, along with two functions that will update it every time a new Node / index is added or removed (it will be fragmented as nodes won't be always contiguous); find an index of a Node in the array: for example by subtracting the address of the Node from the first address of the array.

Here is how a possible interface of a doubly linked list using the above technique would look like:

template <typename T>                          // T type Node in your case
class DList
{
    T** head;                                  // array of pointers of type Node
    int first;                                 // index of first Node
    int last;                                  // index of last Node

    bool* available;                           // array of available indexes 
    int list_size;                             // size of list

    int get_index();                           // search for index with value true in bool available
    void return_index(int i);                  // mark index as free in bool available

    std::ptrdiff_t link_index(T*& l) const;    // get index of Node

    void init();                               // initialize data members
    void create();                             // allocate arrays: head and available

    void clear();                              // delete array elements
    void destroy();                            // delete head

public:
    DList();                                   // call create() and init()
    ~DList();                                  // call clear() and destroy()

    void push_back(T* l);
    void push_front(T* l);
    void insert(T*& ref, T* l);                // insert l before ref

    T* erase(T* l);                            // erase current (i.e. l) and return next
    T* advance(T* l, int n);                   // return n-th link before or after currnet

    std::size_t size() const;
    int capacity () const { return list_size; }
};

You could use that as a benchmark and implement something on your own.

template <typename T>
void DList<T>::push_back(T* l)
{
    if (l == nullptr)
    {
        throw std::invalid_argument("Dlist::push_back()::Null pointer as argument!\n");
    }

    int index = get_index();
    head[index] = l;

    if (last != -1)
    {
        head[last]->next = index;
        head[index]->prev = last;
    }
    else
    {
        first = index;
        head[index]->prev = -1;
    }

    last = index;
    head[index]->next = -1;
}

Answer 13

As an addition to the existing answers of using a previous and a next vector/array, we could build on top of a more dynamically resizing structure, i.e. losing the amortization on the resizing operation.

Why do I think this is suitable? Well, we have gained some advantages by using vectors/arrays, but we got the amortized resizing in return. If we can rid ourselves of the latter, we may have turned the trade entirely in our favor!

Specifically, I am referring to Resizable Arrays in Optimal Time and Space. It's a very interesting data structure, particularly as the basis for other data structures such as the one we are talking about.

Note that I have linked to the technical report, which, unlike the regular paper, also includes the (highly interesting) explanation of how doubly-resizable arrays were achieved.

Answer 14

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