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

Don't use a linked list? Depending on what exactly you do with this data structure (and what fraction of it concurrently) there may be a more suitable implementation. — , Aug 01 '14 at 20:59
the problem is except for this problem linked list is perfect. I have worker threads which pick work from the linked list and a producer which appends work to the thread. A single node contains lots of data partaining to the work that is done(either at that same point in time or the work was allready finished). If I would change the linked list way of approaching the problem I would have the rewrite the entire multi-threading design and also change the way to store my data... — , Aug 01 '14 at 21:04
yes single-directional linked list. As stated in the question singly linked — , Aug 01 '14 at 21:31

score 2 · Accepted Answer · edited Aug 01 '14 at 21:41

2

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.

edited Aug 01 '14 at 21:41

WhozCraig

65,258
11
75
141

answered Aug 01 '14 at 21:03

progrenhard

2,333
2
14
14

I see, let`s say a user can show max 50 nodes on-screen at a given time. Than I have a different linked list which hold the start of the 50 nodes? something like that? – Aug 01 '14 at 21:06
I guess a `NodeList` node will have an array of 50 nodes. In your case if i'm getting what your saying correctly. – progrenhard Aug 01 '14 at 21:07
You can keep count of how many elements are stored in the a node `NodeList` and once it gets to `0` you de-queue it freeing up memory. – progrenhard Aug 01 '14 at 21:09
1

@RG337 this loosely describes how a `std::deque` typically works in C++. Rather than having a linked list of nodes, you have a dynamic array of page links, where each page holds a series of 1..N nodes, N being the page capacity (in this example, 10). It is worth taking the time to investigate the general algorithms for how this is managed if your interested. Part of the benefit includes random access performance that is *much* better than a traditional linked list, as well as outstanding end (front or back) insertion/extraction performance. Worth a look, imho. – WhozCraig Aug 01 '14 at 21:36
2

@RG337 the picture and general description of the algorithm(s) I'm referring to are presented fairly nicely [**in this answer to a different question**](http://stackoverflow.com/a/6292437/1322972) – WhozCraig Aug 01 '14 at 21:45

fast random acces to linked list nodes

1 Answers1