Creating a linked list without pointers but indices

Question

My teacher wants me to create something like linked list but using indices instead of pointers. So the Node contains int data and int index.

Can you drop me a hint how would I do that? I know how to create it with pointers but how to do without them? He mentioned pool as a container though.

Also http://www.cplusplus.com/reference/forward_list/forward_list/ — Havenard, Jul 01 '17 at 09:45
@Havenard, linked list and std::map are different structures, you can't replace one of them by other — devalone, Jul 01 '17 at 10:13
@Havenard, OK, make efficient key-value structure, where keys are sorted and unique using linked list — devalone, Jul 02 '17 at 13:32
@devalone There's also `std::list` which is basically a linked list underneath. But when you have an index you probably want to use `std::map`. — Havenard, Jul 02 '17 at 21:04
@Havenard I know. > But when you have an index you probably want to use std::map When I have index, I use std::vector, when I need key-value structure, I use std::map — devalone, Jul 02 '17 at 21:52
@devalone The thing of `std::vector` is that it requires contiguous memory (reallocs when resized) and contiguous index (0 to n-1), so if your index is a custom range or is not contiguous, even if they are ordered, `std::vector` wont do. — Havenard, Jul 02 '17 at 22:08
@Havenard, why you're telling me it? I know it. I just tried to say, that you should use things for what they are invented for. — devalone, Jul 02 '17 at 22:41
@devalone And I'm saying `std::vector` neither works as a linked list or offers true indexing. — Havenard, Jul 02 '17 at 22:57
@Havenard, yes, just linked list works exactly as linked list — devalone, Jul 03 '17 at 10:21

score 0 · Accepted Answer · answered Jul 01 '17 at 10:09

Your struct Node would be like this

struct Node {
    int data;
    int index; // index of the entry in the pool to the next node
}

You can use a vector or array to create a pool

vector<Node*> pool; // stores the pointer to next nodes

Now to access the next node you can do

Node* nextNode = pool[currNode->index];

Ziezi · Answer 2 · 2017-07-01T10:42:06.063

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

Creating a linked list without pointers but indices

2 Answers2

Linked