通缉:C中非常快速的链接列表

Question

我试图在C中实现一个单独链接的列表.你看到在互联网上浮动的常见实现是类似的

typedef struct {
  int head;
  Node *tail;
} Node;

用像这样的方法

Node cons(int head, Node tail) {
  Node y;
  y.head = head;
  y.tail = malloc(sizeof(Node));
  *y.tail = tail;
}

表现非常重要.有没有办法在C中实现比这更快的链表？例如,摆脱内存分配(y.tail = malloc(sizeof(Node)))应该会显着提高速度.

Answer 1

是的,有...这被称为内存池.类似于线程池.基本上,您在Node类型的程序开头分配一个内存区域.指向此区域的指针存储在数组中.在你的cons函数中,你所做的只是从数组中获取指针.这并没有提高整体速度,但是如果你经常进行内存分配,这会增加程序的响应速度,代价是阵列的某些空间

Answer 2

非常快速地附加到链表？一个绳子(不限于与小的修改字符串)将允许你批量,而不是惩罚追加到列表的末尾分配内存(改善性能比较).

Answer 3

什么操作应该快:插入,检索,所有？总是需要权衡.您的解决方案是否需要可扩展？链接列表不是.

如果您希望/需要坚持链接列表,您可以将其存储到结构数组中,该结构数组具有指示链接列表中下一个条目的索引的字段.插入将非常快,没有任何分配,缺点是您必须事先知道元素的数量 - 或者在表格满了时重新分配表格.

请参阅链接列表上Wikipedia页面的 " 使用节点数组的链接列表 "子部分.