奇数链表表示形式

Question

我正在尝试找到一种方法，通过链表存储指向内存块的无效指针，我遇到了这种表示。

//Initalization
void * list;
//Add void pointer
void add_pointer(void * p) {
  *(void **)p = list;
  list = p;
}
//Remove pointer with address
void remove_pointer(void * p) {
  void ** iter;
  iter = &list;
  while ((*iter != NULL) && (*iter != p)) {
    iter = (void **)*iter;
  }
  if (*iter == p) {
    *iter = *(void **)p;
  }
}

这到底是怎么回事？下一个块的地址是否存储在 void 指针指向的前一个块的数据中？假定列表初始化为 NULL。

另外，这是否假设每个 void 指针的块中没有写入数据？如果有人可以阐明此实现的工作原理，那就太好了，它可以用作链表似乎非常深奥。

Answer 1

它假定节点中的第一个字段是链接指针的插槽，这是一个void *。list是一个void *，它总是指向链表的头部。

add_pointer()函数将一个新节点添加到列表的开头。void *p参数指向要添加的新节点。该函数将void * p 强制转换为void **，以便*(void **)p可以持有void *指针。该函数将上一个头指针存储在此位置为

*(void **)p = list; // list is a void * to the first element

然后，它将list设置为新的第一个元素（即 p）的void *。

现在，remove_pointer()函数从列表中删除一个节点，将指向该节点的void *作为参数。 iter用于迭代列表。它最初被分配list地址，以便*iter将给出链接指针，该指针始终假定为节点中的第一个字段。while 循环iter更新到列表中的下一个节点，直到它在当前节点的链接指针字段中找到p（即要删除的节点）。此时，它更新当前节点的链接指针文件，以指向 p 指向的节点的链接指针字段值，这是由语句完成的

*iter = *(void **)p; // *iter gives the link pointer filed of the current node
                     // p, is the node to be removed, *(void **)p gives the value in  
                     // the link pointer filed of p

Answer 2

它只是假设节点的第一个字段是链接指针的插槽。 它将节点指针强制转换为(void**)，以便它可以在该地址存储void*。

当然，list是指向链表上第一个节点的指针的硬编码位置。

不是最灵活的列表设计。