How to Solve Design Skiplist Problem

Design a Skiplist without using any built-in libraries. A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists. For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way: Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n). See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list Implement the Skiplist class: Note that duplicates may exist in the Skiplist, your code needs to handle this situation.