C -快速随机访问链表节点

Question

我有一个单链表，可以有10000<<节点在任何给定时间。

现在在界面中，我需要按顺序打印这些，用户可以访问单个节点并在该节点上执行操作。显然，如果用户在节点数上选择了一个非常高的数字，那么在能够访问所需的节点之前，它将不得不经过数千个节点。

我目前的修复"翻译"链表到一个数组，因为我的代码是多线程的，我的链表可以在任何给定的时间增长。但是通过代码设计永远不会收缩。

下面是我用来将链表转换为数组的代码。

unsigned int    i=0;
unsigned int    LL_arr_bufsize=128;
my_ll           **LL_arr;
my_ll           *temp;
LL_arr = malloc(LL_arr_bufsize * sizeof(my_ll *));
// err check mem alooc
temp = l_list->next;
while (temp != NULL) {
    LL_arr[i] = temp;
    temp = temp->next;
    if (++i == LL_arr_bufsize) {
        LL_arr_bufsize = LL_arr_bufsize * 2;
        LL_arr = realloc(LL_arr, LL_arr_bufsize * sizeof(my_ll *));
        // err check mem alloc
    }
} 

我基本上想知道是否有一种更好的方法来访问任何给定的节点，而不会导致在访问给定节点之前遍历整个列表的开销…

Answer 1

我可能会被否决，因为我只是想到这个想法，它可能有一些缺陷。

如果你做一个二维节点堆栈。

NodeList -保存一个包含10个节点的数组和它自己的索引。(你可以尝试更大的值)

发生的是NodeList是一个常规的链接列表，您可以取消队列并再次排队。但是你仍然可以得到一些你想要的恒定时间的查找。这是通过一个聪明的搜索函数来完成的，它通常会遍历链表，然而，一旦它到达列表中特定节点的位置，你就可以从它存储的数组中查找常量时间。

如果你想的话，我可能会更清楚地说明这个概念，但我认为你可以很好地了解我想要描述的内容。