skip lists are not bad at all. also, i guess for unrolled-linked-list you might have to have different 'num-items' for different cache sizes.

better would be to have a library of cache-oblivious data-structures & algorithms. google for 'harald-prokop' for some interesting stuff.