c - C 中的链表太慢

Question

我正在用 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
• 英特尔集成显卡

Answer 1

如果你想加速插入操作，那么你不能循环遍历每次附加内容时的整个列表。您的 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;
    }
}