How to output all values stored in a skip list?

[Elledan]

Like the title states. I've got a skip list from which I have to read all values which are stored in it. I do not know the keys of the nodes.

How would I do this?

 

[CSoup]

opps, been a while since I used skiplists.
I think you can get to all values in the skiplist through the base element.

 

[Elledan]

<< opps, been a while since I used skiplists.
I think you can get to all values in the skiplist through the base element. >>


Yeah, that's probably the best way. I'm only lacking the necessary information to implement it.

Ah well, this would be a good time to read up on linked (skip) lists

 

[CSoup]

I think it should be pretty simple. The bottom of the skip list contains all nodes in sorted order. You can easily get a pointer to this first bottom element easily since you can use the pointer that is used for searching. After you know the first element, you just have to keep tracing throgh the list like you do with normal linked lists till you hit NULL.

 

[Elledan]

Yup, it sounds really simple, but since I have a hard time grasping the implementation behind linked lists, it's more difficult to me than it sounds

I'll be fine, though. I really need to brush up on my 'linked-list'-skills, anyway =)

 

[m0ti]

yeah, the answer is what CSoup suggested. Here's the basic layout of a skip list.


A ---- ---- C
| |
A ----B---- C
| | |
A ----B-----C----D

EDIT: Of course, my spacing doesn't work out ok. but you get the idea

As a quick reminder, assuming that you built a random skip list the algorithm for inserting the nodes is simple:

int insert(top left node, node to be inserted)
1) go right till the next node is larger than the current node
2) if current node can go down, then call insert(current node.down, node to be inserted) (if returns 1 then toss a coin. If the result is 1, insert the new node between the current node and the next node, and return 1. otherwise return 0).
3) (we're at the bottom layer): insert the node between the one behind it and the one after it. return 1.

That's just an example for random skip lists. In general, every layer of a skip list includes at least all of the elements of the layer above it, in general it contains twice as many (so that searches are indeed in log time). As a result of this, all data is stored in a sorted order at the lowest level.

If you want an easy way to go through all the list just go straight down from the first node, until you can't go down anymore, and then iterate over the bottom layer. As a note: many skip list implementations use sentinels at both ends (-Infinity at the left end, and +Infinity at the right end).