快速随机访问链表节点

I have a singly linked list which can have 10000<< nodes at any given time.

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

Now in the interface I need to print these in order and a user can acces a single node and perform operations on that node. Obviously if the user chooses a very high number on the node count it will have to go over thousands of node before being able to acces the desired node.

现在在接口中我需要按顺序打印这些,用户可以访问单个节点并在该节点上执行操作。显然,如果用户在节点数上选择一个非常高的数字,则在能够访问所需节点之前必须经过数千个节点。

My current fix "translates" the linked list to an array, since my code is multithreaded my linked list can grow at any given time. But by code design never shrink.

我当前的修复程序将链表“转换”为数组,因为我的代码是多线程的,我的链表可以在任何给定时间增长。但是代码设计永远不会缩小。

Here is code I use to translate linked list to array.

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

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
    }

}

What am I basically wondering if there is a better way to acces any given node without incuring the overhead of traversing the entire list before a given node can be accessed...

我基本上想知道是否有更好的方法来访问任何给定节点,而不会在访问给定节点之前产生遍历整个列表的开销...

1 个解决方案

#1

I will probably get down voted because I literally just thought of this idea and it might have some flaws. Here it goes.

我可能会投票,因为我只是想到了这个想法,它可能有一些缺陷。在这里。

What if you do a two dimensional node stack. Here me out.

如果你做一个二维节点堆栈怎么办?我出去了。

NodeList - holds an array of 10 nodes and it's own index. ( you can experiment with bigger values)

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

What happens is that NodeList is a regular link list that you can de-queue and queue again. But you can get still some of that constant time look-upness that you are looking for. This is done with a clever search function that goes goes through the link list normally however, once it goes to the location of where your particular node is being held in the list you get that constant time look up from the array it stores.

会发生什么是NodeList是一个常规链接列表,您可以再次排队和排队。但是你可以获得一些你正在寻找的恒定时间查找。这是通过一个聪明的搜索功能来完成的,它通常会通过链接列表,但是,一旦它到达您的特定节点在列表中保存的位置,您将从它存储的数组中查找恒定时间。

I can probably clarify more of this concept if you want but I think you can get a good picture of what I'm going for with the description.

如果你愿意,我可以澄清更多这个概念,但我认为你可以很好地了解我的描述。

#1