The skip list is my favorite data type. This may be because of some exposure to AVL trees back during my college days. Self balancing trees are wonderful, but they can be difficult to reason about. If someone was to ask me what goes on when a value is inserted or deleted from an AVL tree, my answer would probably be “magic occurs”, and frankly, its magic I don’t care to dabble in.
Skip lists, on the other hand, are built on nice, classic linked lists. Linked lists get a bad rap when compared to List structures backed by an array, but they have their advantages. When comparing them to trees, it is important to realize that the trees are linked lists themselves.