我正在用 C 开发一个应用程序。这个应用程序需要快速插入一个链表,但是,由于下面的示例代码,我只能得到 16384 或 2^14 在 0.5 秒内插入。我每秒至少需要 100000 - 1000000 次插入。我想知道是否有任何方法可以提高链表的性能。我在想我应该向链表添加一个“索引”,就像数组索引一样,并从那里附加它。
注意:这是一个单链经典链表。
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define NUM_OF_ELEMENTS 32768
struct Node {
int data;
struct Node* next;
};
struct Node* create_list(int genesis_data) {
struct Node* list = (struct Node*)malloc(sizeof(struct Node));
list->data = genesis_data;
list->next = NULL;
return list;
}
void append(struct Node* head, int _data_) {
struct Node* new_block = (struct Node*)malloc(sizeof(struct Node));
struct Node* current = (struct Node*)malloc(sizeof(struct Node));
current = head;
new_block->data = _data_;
new_block->next = NULL;
if(head->next == NULL) {
head->next = new_block;
}
else {
while(true) {
if(current->next == NULL) {
current->next = new_block;
break;
}
else {
current = current->next;
}
}
}
}
void print_list_data(struct Node* head) {
struct Node* current = (struct Node*)malloc(sizeof(struct Node));
current = head;
while(true) {
if(current->next == NULL) {
printf("Node: %d\n", current->data);
break;
}
else {
printf("Node: %d\n", current->data);
current = current->next;
}
}
}
int main() {
struct Node* list = create_list(15);
printf("List created!\n");
append(list, 5);
printf("Single element appended to list!\n");
printf("Appending %d items to the list...\n", NUM_OF_ELEMENTS);
double t1 = clock();
for(int x = 0; x < NUM_OF_ELEMENTS; x++) {
append(list, 5);
}
double t2 = clock();
printf("Time taken to append %d elements to the list: %f\n", NUM_OF_ELEMENTS, (t2-t1)/CLOCKS_PER_SEC);
//print_list_data(list); // to print data to the list
return 0;
}
规范:
- 16 GB DDR4 内存
- 英特尔酷睿 I7
- 英特尔集成显卡
最佳答案
如果你想加速插入操作,那么你不能循环遍历
每次附加内容时的整个列表。您的 append
函数添加了新的
元素位于列表的末尾,因此头节点可以有一个指向
列表尾部:
struct Node {
int data;
struct Node *next;
struct Node *tail; // used only by the head node
};
struct Node* create_list(int genesis_data) {
struct Node* list = malloc(sizeof *list);
if(list == NULL)
return NULL;
list->data = genesis_data;
list->next = NULL;
list->tail = list;
return list;
}
同时删除这一行
struct Node* current = (struct Node*)malloc(sizeof(struct Node));
从你的 append
和 print_list_data
函数中,除了泄漏内存外没有任何作用。和
不要使用以下划线开头的变量名,变量名
以下划线开头由语言/编译器保留。
int append(struct Node* head, int data) {
if(head == NULL)
return 0;
struct Node *node = malloc(sizeof *node);
if(node == NULL)
return 0;
node->data = data;
node->next = NULL;
head->tail->next = node;
head->tail = node; // updating tail of head
return 1;
}
这个函数在 O(1)
中。但它是有代价的:你制作了你的节点
结构更大,需要更多空间。
当然,如果你删除了节点,而你碰巧删除了头部,请不要忘记
更新新头部的 tail
成员。
如果你想要插入操作的速度,我可能会使用数组 而不是链表。
编辑
作为Dave S在评论中指出,这个解决方案是有代价的,
结构变得更大,你有很多空间浪费,因为只有头部
使用 tail
成员。另一种解决方案是将链表环绕
第二个结构包含指向尾部的指针:
struct Node {
int data;
struct Node *next;
};
struct List {
struct Node *head;
struct Node *tail;
}
struct Node* create_node(int genesis_data) {
struct Node* list = malloc(sizeof *list);
if(list == NULL)
return NULL;
list->data = genesis_data;
list->next = NULL;
return list;
}
struct List *create_list(int genesis_data)
{
struct List *list = malloc(sizeof *list);
if(list == NULL)
return NULL;
list->head = create_node(genesis_data);
if(list->head == NULL)
{
free(list);
return NULL;
}
list->tail = list->head;
return list;
}
int append(struct List* list, int data) {
if(list == NULL)
return 0;
struct Node *node = malloc(sizeof *node);
if(node == NULL)
return 0;
node->data = data;
node->next = NULL;
list->tail->next = node;
list->tail = node; // updating tail of head
return 1;
}
void print_list_data(struct List* list) {
if(list == NULL)
return;
struct Node *current = list->head;
while(current)
{
printf("Node: %d\n", current->data);
current = current->next;
}
}
关于c - C 中的链表太慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49702933/