class Node:
    def __init__(self, data, level=0):
        self.data = data
        self.next = [None] * level
    
    def __str__(self):
        return "Node({}, {})".format(self.data, len(self.next))

class SkipList:
    def __init__(self, max_level=8):
        self.max_level = max_level
        node = Node(Node, max_level)
        self.head = node
        self.length = 0

    def __len__(self):
        return self.length

    def __getitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("UnrolledLinkedList assignment index out of range")
        else:
            count = 0
            node = self.head.next[0]
            while count < index:
                node = node.next[0]
                count += 1
            return node.data

    def locate(self, value):
        node = self.head
        # 由于索引從0開始，因此第i層級(jí)的索引為i-1
        level = self.max_level - 1
        while level >= 0:
            while node.next[level] != None and node.next[level].data < value:
                # 平移到當(dāng)前層的后繼結(jié)點(diǎn)
                node = node.next[level]
            # 下移進(jìn)入下一層
            level -= 1
        if node.next[0].data == value:
            return node.next[0]
        else:
            raise ValueError("{} is not in skip list".format(value))

    def random_level(self, max_level):
        num = random.randint(1, 2**max_level -1)
        lognum = math.log(num, 2)
        level = int(math.floor(lognum))
        return max_level - level

    def update_list(self, data):
        update = [None] * self.max_level
        node = self.head
        level = self.max_level - 1
        while level >= 0:
            while node.next[level] != None and node.next[level].data < data:
                node = node.next[level]
            update[level] = node
            level -= 1
        return update

    def insert_node(self, data):
        # 產(chǎn)生隨機(jī) level，并構(gòu)造結(jié)點(diǎn)
        level = self.random_level(self.max_level)
        node = Node(data, level)
        # 獲取 update 列表
        update = self.update_list(data)
        # 插入結(jié)點(diǎn)
        if len(update) == 0 or update[0].next[0] == None or update[0].next[0].data != data:
            self.length += 1
            for i in range(level):
                node.next[i] = update[i].next[i]
                update[i].next[i] = node

    def delete_node(self, data):
        # 獲取 update 列表
        update = self.update_list(data)
        if len(update) > 0:
            node = update[0].next[0]
            # 刪除指定元素結(jié)點(diǎn)
            if node != None and node.data == data:
                self.length -= 1
                for i in range(len(node.next)):
                    update[i].next[i] = node.next[i]
                del node

def get_level(self, level):
? ? ? ? """輔助函數(shù)，用于根據(jù)給定層構(gòu)造結(jié)果字符串"""
? ? ? ? node = self.head.next[level]
? ? ? ? result = ''
? ? ? ? while node:
? ? ? ? ? ? result = result + str(node.data) + '-->'
? ? ? ? ? ? node = node.next[level]
? ? ? ? result += 'None'
? ? ? ? return result

? ? def print_level(self, level):
? ? ? ? print('level {}'.format(level))
? ? ? ? result = self.get_level(level)
? ? ? ? print(result)

    def __str__(self):
        result = ''
        for i in list(range(self.max_level))[self.max_level-1:0:-1]:
            result = result + self.get_level(i) + '\n'
        result += self.get_level(0)
        return result

sl = SkipList(4)
for i in range(0, 30, 3):
    sl.insert_node(i)

print('跳表 sl 各層元素為：')
print(sl)
print('跳表 sl 長(zhǎng)度為：', len(sl))
print('跳表 sl 第 2 個(gè)元素為：', sl[2])

跳表 sl 各層元素為：
9-->None
0-->9-->18-->None
0-->9-->18-->27-->None
0-->3-->6-->9-->12-->15-->18-->21-->24-->27-->None
跳表 sl 長(zhǎng)度為： 10
跳表 sl 第 2 個(gè)元素為： 6

# 插入元素
sl.insert_node(14)
print('在跳表 sl 中插入數(shù)據(jù) 14 后：')
print(sl)
# 刪除元素
sl.delete_node(14)
print('刪除跳表 sl 中數(shù)據(jù) 14 后：')
print(sl)
# 查找數(shù)據(jù)元素 15
print('查找跳表 sl 中數(shù)據(jù)元素 15：', sl.locate(15))

在跳表 sl 中插入數(shù)據(jù) 14 后：
9-->None
0-->9-->18-->None
0-->9-->14-->18-->27-->None
0-->3-->6-->9-->12-->14-->15-->18-->21-->24-->27-->None
刪除跳表 sl 中數(shù)據(jù) 14 后：
9-->None
0-->9-->18-->None
0-->9-->18-->27-->None
0-->3-->6-->9-->12-->15-->18-->21-->24-->27-->None
查找跳表 sl 中數(shù)據(jù)元素 15： Node(15, 1)