c - 通缉 : Very Fast Linked Lists in 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.tai​​l = malloc(sizeof(Node))) 应该会显着提高速度。

Answer 1

是的，有...这称为内存池。类似于线程池。基本上，您在类型为 Node 的程序的开头分配一 block 内存区域。指向该区域的指针存储在一个数组中。在你的 cons 函数中，你所做的就是从数组中获取指针。这不会提高整体速度，但如果您有频繁的内存分配，这将以数组的一些空间为代价提高程序的响应能力