最新做了一些题，碰巧看到一道题是实现一个跳表， 对 跳表 早有耳闻，从 ES， Redis 的一些资料中隐约看到过这个名字，以前粗略了解了一下跳表的接口和复杂度，觉得是个小平衡树，真正学习后发现它比平衡树简单多了，但是性能却不差平衡树，真是一种代码性价比极高的数据结构。
    看别人题解实现跳表代码很少，觉得是我上我也行的程度。就找了几篇文章学习，自己动手实现，写完一对比，行也不行，行的是功能都实现了，不行的是别人的版本速度比我的版本快10倍！而且代码巧妙又优雅。
    先贴一下我的实现

    1. import random
    3. MAX_LEVEL = 16
    6. class Node:
    7.     def __init__(self, val=0):
    8.         self.val = val
    9.         self.right = None
    10.         self.down = None
    13. def get_level():
    14.     # 1/2 是最下层，1/4是第二层。。。。
    15.     init_num = 1
    16.     p = 1 / 2
    17.     while random.random() < p and init_num < MAX_LEVEL:
    18.         init_num += 1
    19.     return init_num
    22. class Skiplist:
    24.     def __init__(self):
    25.         self.left = [Node(-1) for _ in range(16)]
    26.         for i in range(15):
    27.             self.left[i].down = self.left[i + 1]
    28.         self.head = self.left[0]
    30.     def search(self, target: int) -> bool:
    31.         prv = self.head
    32.         while prv:
    33.             if prv.val == target:
    34.                 return True
    35.             elif not prv.right or prv.right.val > target:
    36.                 prv = prv.down
    37.             else:
    38.                 prv = prv.right
    39.         return False
    41.     def add(self, num: int) -> None:
    42.         level = get_level()  # 3  self.left[13]
    43.         print(level)
    44.         level_head = self.head
    45.         for _ in range(MAX_LEVEL - level):
    46.             level_head = level_head.down
    47.         self._add(level_head, num)
    49.     def _add(self, prv_head, num):
    50.         while prv_head:
    51.             if not prv_head.right or num < prv_head.right.val:
    52.                 right = prv_head.right
    53.                 node = Node(num)
    54.                 prv_head.right = node
    55.                 node.right = right
    56.                 node.down = self._add(prv_head.down, num)
    57.                 return node
    58.             else:
    59.                 prv_head = prv_head.right
    61.     def erase(self, num: int) -> bool:
    62.         is_removed = False
    64.         prv = self.head
    65.         while prv:
    66.             if not prv.right or prv.right.val > num:
    67.                 prv = prv.down
    68.             elif prv.right.val == num:
    69.                 prv.right = prv.right.right
    70.                 prv = prv.down
    71.                 is_removed = True
    72.             else:
    73.                 prv = prv.right
    74.         return is_removed
    76.     def print(self):
    77.         _list = [[] for _ in range(MAX_LEVEL)]
    78.         for i in range(MAX_LEVEL):
    79.             cur = self.left[i]
    80.             while cur:
    81.                 _list[i].append(cur.val)
    82.                 cur = cur.right
    83.             print(_list[i], len(_list[i]))
    86. sk = Skiplist()
    87. for i in range(1, 100):
    88.     sk.add(i)
    89. print(sk.erase(0))
    90. sk.print()

    别人的实现

    1. import random
    4. class Node:
    5.     def __init__(self, val=0):
    6.         self.val = val
    7.         self.right = None
    8.         self.down = None
    11. class Skiplist:
    13.     def __init__(self):
    14.         self.left = [Node(-1) for _ in range(16)]
    15.         self.right = [Node(20001) for _ in range(16)]
    16.         for i in range(15):
    17.             self.left[i].right = self.right[i]
    18.             self.left[i].down = self.left[i + 1]
    19.             self.right[i].down = self.right[i + 1]
    20.         self.left[-1].right = self.right[-1]
    21.         self.head = self.left[0]
    23.     def search(self, target: int) -> bool:
    24.         cur = self.head
    25.         while cur:
    26.             if cur.right.val > target:
    27.                 cur = cur.down
    28.             elif cur.right.val < target:
    29.                 cur = cur.right
    30.             else:
    31.                 return True
    32.         return False
    34.     def add(self, num: int) -> None:
    35.         cur = self.head
    36.         stack = []
    38.         while cur:
    39.             if cur.right.val >= num:
    40.                 stack.append(cur)
    41.                 cur = cur.down
    42.             else:
    43.                 cur = cur.right
    44.         pre = None
    46.         while stack:
    47.             cur = stack.pop()
    48.             node = Node(num)
    49.             node.right = cur.right
    50.             cur.right = node
    51.             if pre:
    52.                 node.down = pre
    53.             pre = node
    54.             if random.randint(0, 1):
    55.                 break
    57.     def erase(self, num: int) -> bool:
    58.         cur = self.head
    59.         is_removed = False
    60.         while cur:
    61.             if cur.right.val >= num:
    62.                 if cur.right.val == num:
    63.                     is_removed = True
    64.                     cur.right = cur.right.right
    65.                 cur = cur.down
    66.             else:
    67.                 cur = cur.right
    68.         return is_removed
    70.     def print(self):
    71.         _list = [[] for _ in range(16)]
    72.         for i in range(16):
    73.             cur = self.left[i]
    74.             while cur:
    75.                 _list[i].append(cur.val)
    76.                 cur = cur.right
    77.             print(_list[i], len(_list[i]))
    80. sk = Skiplist()
    81. for i in range(1, 100):
    82.     sk.add(i)
    83. print(sk.search(99))
    84. sk.print()