创建无指针链表，但指数

Question

我的老师希望我创造这样的链表，但使用索引来代替指针。所以Node包含int data和int index。

你可以将我暗示我该怎么做？我知道如何用指针创建它，但如何在没有它们的情况下做到这一点？尽管他提到游泳池是一个容器。

Answer 1

你的结构Node会是这样

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

您可以使用vector或阵列创建池

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

我们进入下一个节点，你可以做

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

Answer 2

一种可能的方法是使用一组Nodes wh ERE每个节点存储的（数组）索引到prev和nextNode。因此，你的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阵列，实现一些簿记阵列中获得和免费空间：例如bool阵列存储所述Node阵列中的未占用的索引，具有两个功能，这将每一个新的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; 
}