代码之家 › 专栏 › 技术社区 › Michael Dickens

通缉:非常快速的链表在C

linked-list performance c

Michael Dickens · 技术社区 · 14 年前

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))

8 回复 | 直到 14 年前

Laz 14 年前

是的,有。。。这称为内存池。类似于线程池。基本上,在Node类型的程序开始时分配一个内存区域。指向此区域的指针存储在数组中。在cons函数中,只需从数组中获取指针。这不会提高总体速度,但如果频繁分配内存,则会增加程序的响应速度,但会为数组占用一些空间

Yann Ramin 14 年前

很快附加到链表?A rope

philant 14 年前

什么操作应该是快速的:插入,检索,全部?总有一种取舍。您的解决方案是否需要可扩展?不支持链表。

如果您想/需要粘贴到一个链表,您可以将它存储到一个结构数组中,该数组中有一个字段指示链表中下一个条目的索引。插入将非常快,没有任何分配,缺点是您必须提前知道元素的数量—或者在表满时重新分配表。

请参阅“ 使用节点数组的链表 the Wikipedia page on linked list .

Jon L 14 年前

撇开内存方面的问题不谈,还有一些关于加快单链接列表速度的想法。

typdef struct _node {
     ...
     struct _node *next;
} NODE;

大多数实现都有一个 void *

列表插入必须连接指针。为了简单地添加节点(并且忽略添加有效载荷),如果节点在列表的头部或尾部,则有1个分配,并且如果它在中间,则有2个分配。没有什么办法可以绕过这个问题。

通过将其实现为跳过列表,可以更快地进行遍历( http://en.wikipedia.org/wiki/Skip_list

Jeff Meatball Yang 14 年前

如果您关心malloc碎片,您可以请求一个大的倍数大小的节点,并在每次复制节点值时保持按sizeof(Node)递增指针。

Nicolas Viennot 14 年前

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

(无额外内存分配)

curoo 14 年前

还要检查此单链表实现的速度:

http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html

adf88 14 年前

推荐文章

GabrielChu · 如何释放带有指针的链表

7 年前

Diksha · 在C语言中将文本文件转换为单链表时,每次插入时头部都会更新

7 年前

Link · 向链表中添加结构似乎不起作用

7 年前

Jheel rathod · 带有构造函数的ocaml递归类型记录

7 年前

amr125 · 在链表中插入元素-索引不存在

7 年前

JOSI · 求职面试的基本内容-使用链表、数组

7 年前

Sikorski · 是否有必要对仅用于删除操作的列表进行同步

7 年前

Harrison Tran LamBigini · scanf无法从用户处获取2个输入:整数和字符串[重复]

7 年前

Henry Williams · C-赋值后访问struct属性导致分段错误

7 年前

Pushkar Mahajan · 如何避免分段核心转储错误?

7 年前