c - C 中存储字符串的链表或数组

Question

在 C 中，我需要存储一个可能相对较大(数千个项目)的短字符串 (char*) 列表。
字符串可以删除或插入，但不能修改，并且顺序并不重要。
我不知道什么是更有效的数据结构来做到这一点。
我可以使用一个结构:

struct node_s {
  char *str;
  node_s *next;
}

或 char * 数组:

char **strings;

我不需要直接访问字符串，我只需要它们存在，因为旁边的另一个数据结构(基数特里)维护着字符串某些部分的指针。

Answer 1

当您在初始化时不知道条目的确切数量时，使用链表通常比使用数组更好。

数组有固定的大小。当您不知道将有多少条目并且想要使用数组时，您有两种选择。要么分配一个比您需要的任何东西都大得多的数组，这会浪费大量内存(而且，通常很难提前知道合理的上限应该是多少)。或者你从一个小数组开始，等到它满了。然后分配一个更大的新数组，将所有条目复制到新数组并释放旧数组，这是对 CPU 周期的巨大浪费。

但是使用链接列表，您就不会遇到这个问题，因为它们可以动态增长和收缩。

但要注意各种操作运行时的差异。

在数组中，通过索引获取元素非常快。但是，删除具有特定索引的元素而不留下空条目的成本非常昂贵，因为后面的每个元素都必须向后移动一个索引。在中间插入一个条目而不覆盖现有条目同样昂贵，因为您必须将后面的所有内容向前移动一位。

使用链表，删除或插入中间的节点速度很快(当您已经拥有其前驱节点时)，因为除了插入的节点及其前驱节点之外，不需要触及任何节点。但是找到必须执行此操作的节点可能会很昂贵，因为您必须跟踪之前的所有节点的链接。

当您需要快速查找和快速插入/删除时，请使用 binary tree是一个很好的妥协。