> See also: > - Reference # Skip Lists A skip list is a data structure that allows for efficient search, insertion and deletion of elements in a sorted list. It is a probabilistic data structure, meaning that its average time complexity is determined through a probabilistic analysis. In a skip list, elements are organized in layers, with each layer having a smaller number of elements than the one below it. The bottom layer is a regular linked list, while the layers above it contain “skipping” links that allow for fast navigation to elements that are far apart in the bottom layer. The idea behind this is to allow for quick traversal to the desired element, reducing the average number of steps needed to reach it. Skip lists have an average time complexity of $O(\log n)$ for search, insertion and deletion, which is similar to that of balanced trees, such as AVL trees and red-black trees, but with the advantage of simpler implementation and lower overhead. - Because skip lists are a probabilistic data structure, it is more accurate to say that they have a “high probability” of having an $O(\log n)$ runtime. The “perfect” skip list structure should have $\log_2 n$ express linked list structures For example, the following skip list contains 9 elements, so: $\log_2 n= \log_2 9 = 3.17 \approx 3$ ![[Pasted image 20240305160556.png|500]] --- - While we could perform a binary search on an array, we do not have the benefit of indices when using a linked list and would be forced to travserse through each element individually unless another method was available. ## Inserting Into Express List(s) Skip lists are implemented using a technique called “coin flipping.” In this technique, a random number is generated for each insertion to determine the number of layers the new element will occupy. This means that, on average, each element will be in log(n) layers, where n is the number of elements in the bottom layer.