C代码:解析到LinkedList结尾的有效方法

Question

我有一个结构数据,这将是一个链接的消息列表.对于每个新消息,我需要在链接列表的最后一个附加.我有一个计数器,我知道有多少消息存在.而不是解析直到链接列表的结尾.有没有更好的方法来达到链接列表中的具体位置？

struct Data {
   char            *message;
   struct Data     *next;
}data;

int total_message;

现在我解析如下:

struct Data *traverse;

while(traverse->next != NULL)
    traverse = traverse->next;

我也在下面试过,我不确定为什么这个错误在逻辑上对我来说似乎是正确的.

data[total_messages - 1].next = new_data;

除了将指针存储到Last Message之外,还有更好的方法吗？

Answer 1

考虑维护指向链表尾部的指针.

data * head = NULL;
data * tail = NULL;
void Append(data * entry) {
  if (!head) {
    head = entry;
  }
  if (tail) {
    tail->next = entry;
  }
  tail = entry;
}

为什么遍历(如问题中)是不好的？

如果我们只维护head和消息的数量n,那么对于每个追加,我们必须遍历n链接节点head- 从那个O(n)操作开始 - 效率稍低.如果添加到列表的尾部是一个频繁的操作 - 就像你的情况似乎 - 那么保持尾指针是有效的.在空间方面,维护计数器与维护指针相同.

以下为什么不好？

data[total_messages - 1].next = new_data;

这是一个数组符号.数组是连续的内存块.在链表中,节点可以在内存中的任何位置,它们不能以数组表示法访问.