c - 添加到双向链表的头部

Question

我有以下内容:

typedef struct value value;

struct value{
  value* prev;
  value* next;
  int value;
};

...
//ent = entry
if(entry_head == NULL) { 
 entry_head = ent;
 entry_tail = ent;
 entry_tail->prev = NULL;
}
else { // add to top
 entry_head = ent
 entry_tail = entry_tail->next;
}

当我向列表中插入一些值时，我得到以下结果。

Expected: b         Result: a
          a                 b

如何修改它以便新添加的节点链接到先前节点的顶部？

Answer 1

您的代码没有设置足够的指针。一般来说，必须保证新节点的prev是正确的； 下一个是正确的；上一个条目的 next 是正确的；并且下一个条目的 prev 是正确的(如果上一个或下一个条目为 NULL，请小心)。

假设全局变量是:

value *entry_head = NULL;
value *entry_tail = NULL;

然后插入新值*ent(已经用值初始化)的代码是:

if (entry_head == NULL)
{
    assert(entry_tail == NULL);
    entry_head = ent;
    entry_tail = ent;
    ent->next = NULL;
    ent->prev = NULL;
}
else
{
    assert(entry_tail != NULL);
    ent->next = entry_head;
    ent->prev = NULL;
    entry_head->prev = ent;
    entry_head = ent;
}

类似的代码可用于在列表的尾部插入，稍微不同的代码会在列表中现有条目之前或之后插入。