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 是一个常规链接列表，您可以将其取消排队并再次排队。但您仍然可以获得一些您正在寻找的恒定时间查找。这是通过一个聪明的搜索函数完成的，该函数通常会遍历链接列表，但是，一旦它到达列表中保存特定节点的位置，您就可以从它存储的数组中进行恒定时间的查找。

如果您愿意，我可能可以进一步澄清这个概念，但我认为您可以通过描述更好地了解我想要的内容。