# Why don't nodes carry as many pointers as possible in a skip list?

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:

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.

• 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?
– Evil
Jan 17, 2016 at 20:09
• 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, 2016 at 21:01
• "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, 2016 at 21:13
• 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, 2016 at 21:16
• @D.W. It wouldn't be a tree structure because each node could be accessible via multiple paths. Jan 18, 2016 at 4:49

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.

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.

• 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. Jan 17, 2016 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?
– Evil
Jan 17, 2016 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 :) Jan 17, 2016 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?
– Evil
Jan 17, 2016 at 20:02
• I've added a big EDIT to the question. I hope this is clearer. Jan 17, 2016 at 20:08