创建一个没有指针但有索引的链表

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数组，其中每个节点存储一个(数组(索引到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数组，实现一些簿记来获取和释放数组中的空间：例如，将未占用的索引存储在Node数组中的bool数组，以及每次添加或删除新的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;
}