Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list:

enter image description here

Wouldn't it make more sense to have every node carry 4 pointers (since this is the height of this specific example)? For instance, node with value 2 would also have pointers to nodes 4, 6 and 7 and not just to node 3.

I'm asking because I need a data structure that would allow me to traverse the list as quickly as possible. Having each node carry as many pointers as possible would allow me to carry out lots of parallel requests. Also, each arrow in my implementation is actually a network call, so if I can achieve higher concurrency to retrieve all 10 items would be best.

share|cite|improve this question
    
So order is by time that is why you simply add to head? 10 feeds are to be send at once and further portions are 10 each? – EvilJS Jan 17 at 20:09
2  
You using a linked list to store the feed items does not mean you have to use synchronous iteration to retrieve items. The two issues are completely orthogonal. An iterator can spawn a new asynchronous task for every item. You should go to Stack Overflow for help on that. – Raphael Jan 17 at 21:01
2  
"Wouldn't it make more sense to have every node carry 4 pointers?" - no, because then it wouldn't be a skip list any more. If you want a fixed number of pointers per node, then you are looking for a tree data structure. There are lots of candidates. They have various advantages and disadvantages compared to a skip list -- I suggest you do some reading. – D.W. Jan 17 at 21:13
2  
Or, to put it another way: I think you have an XY problem. Rather than starting by assuming you need to use skip lists, why not describe your core problem without necessarily assuming what approach will be best and let us identify solutions? At this point I'd suggest that you ask a new question for that, rather than try to edit this question into that form (to avoid invalidating existing answers). It is helpful to describe what approaches you've considered and why you've rejected them. – D.W. Jan 17 at 21:16
    
@D.W. It wouldn't be a tree structure because each node could be accessible via multiple paths. – immibis Jan 18 at 4:49
up vote 5 down vote accepted

In the usual way, where each node carries $i$ pointers with probability $2^{-i}$, the average node has size $O(1)$, so the total space used by the skip list is $O(n)$. If each node carried pointers at every level, then each node would have $\theta(\log n)$ pointers in it, since that is the expected height of a skip list with $n$ nodes. The total space used would thus be $\theta(n \log n)$.

A skip list of one million nodes would thus be using roughly 10 times as much space.

share|cite|improve this answer
    
Thanks this is actually what I thought. – Luca Matteis Jan 17 at 21:27

And how would you like to manage this?
It will resemble a tree, not skip list, and memory overhead will be bigger.
Traversal time will decrease in some cases, but insertion time will increase.
Traversing over all elements will not change, you still check them all.

If you want to make concurent task, why bother with skip list?
Just make ten pointers from root and deal them among the threads.

Skip list gives faster search but lower overhead for insertion. It is amortized time. But going through all items does not benefit from additional pointers.

share|cite|improve this answer
    
Thanks that makes sense. Would you know of a data structure that allows me to retrieve the head-closest portion of the list with greater concurrency, than say, the rest of the list? Perhaps something that decreases concurrency as you leave the head. If I just have each item point to the next 10 items, the first 10 items are concurrent, but then traversing the rest is sequential. Also, insertions are only to the head of the list, and I can't modify anything inside the list for each insertion. Perhaps deletions are needed but not for now. – Luca Matteis Jan 17 at 19:40
    
Ok. Please edit your question, as requirements are changing a bit by now. Maybe array of lists? Do you care about the order? – EvilJS Jan 17 at 19:52
    
Yes will do thanks. Yes order is important. Essentially imagine a twitter feed. Users are interested in getting the latest items of the feed and not the oldest ones. I need something that starts with high concurrency, and gradually is less concurrent (therefore more sequential) as it reaches the end. I don't even know if something like this is possible :) – Luca Matteis Jan 17 at 19:58
    
So you have like 10 constant fixed threads on your own? Cannot modify anything else than head - you mean structure? Elements must stay there? Sorry, I do not use/have seen twitter (I do not deny it exists though), why do you intend to decrease concurency? – EvilJS Jan 17 at 20:02
    
I've added a big EDIT to the question. I hope this is clearer. – Luca Matteis Jan 17 at 20:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.