添加到双向链表的头部

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 是正确的；前一个条目的 next 是正确的；并且下一个条目的 prev 是正确的（如果前一个或下一个条目为 NULL，请小心）。

假设全局变量是：

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

那么插入一个新的 value *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;
}

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

添加到双向链表的头部

Adding to the head in a doubly linked list

c

linked-list