Evenly placed Skip pointers

Question

I was reading about skip pointers and someone suggested that it is best to put evenly spaced sqrt(len of list) skip pointers. Can someone tell me what "evenly spaced" means here? I will also like to see the code of doing such a thing in Java or Python

Answer 1

I think your friend was talking about skip lists. Usually the skip pointers are placed randomly through the list. Evenly spaced pointers refers to deterministically spacing them throughout the list instead of randomly placing them. Such a scheme would probably give faster reads, but would probably require more calculation when writing to the list.

Answer 2

def add_skips(posting_list):
post_list_with_skips = []
skip_count = math.floor(math.sqrt(len(posting_list)))
pos_index = 0
skip_period = math.floor(len(posting_list) / skip_count)
# -1 because of list indexing starts with 0
skip_index = skip_period - 1
while pos_index < len(posting_list):
    if pos_index == skip_index:
        post_list_with_skips.append([posting_list[pos_index], 1])
        skip_index += skip_period
    else:
        post_list_with_skips.append([posting_list[pos_index], 0])
    pos_index += 1
return post_list_with_skips