創建無指針鏈表，但指數

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