ポインタではなくインデックスを使用したリンクリストの作成

Question

先生は、リンクリストのようなものを作成して、ポインタの代わりにインデックスを使用したいと考えました。したがって、Nodeには、int dataとint indexが含まれています。

あなたは私にそのヒントを教えてもらえますか？私はポインタでそれを作成する方法を知っているが、それらなしで行う方法は？彼はコンテナとしてプールを言いました。

Answer 1

あなたのstruct Nodeはあなたが行うことができます今すぐ次のノードにアクセスするために、プール

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

を作成するために vectorまたは配列を使用することができ、この

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

ようになる

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

Answer 2

可能な方法は、Nodes whの配列を使用することです各ノードは、prevおよびnextNodeに（アレイ）インデックスを格納する。例えばbool配列：また、あなたはおそらく、アレイ内のと自由スペースを得るにいくつかの簿記を実装し、動的にNode配列を割り当てる必要があります

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

：したがって、あなたのNodeは、次のようになります新しいNode/indexが追加または削除されるたびに更新される2つの関数とともに、Node配列に空のインデックスを格納します（ノードが必ずしも連続しているわけではないので断片化します）。アレイ内のNodeのインデックスを探します。たとえば、アレイの最初のアドレスからNodeのアドレスを減算します。あなたはベンチマークとしてそれを使用し、自分で何かを実装することができ

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

：ここ

は、上記の技術を使用して二重リンクリストの可能なインタフェースは次のようになります方法です。

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