fast random acces to linked list nodes

Question

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

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...

Answer 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)

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.

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.