A skip list is an efficient data structure that arranges the elements in a list in such a way that the search and update takes O(nlogn) time on average. n is the number of items in the list.

We would cover the following

**1. How Skip Lists Work**

First of all, we define a skip list S for a map M consists of a series of lists {S_{0}, S_{1}, S_{2}, . . . , S_{h})

Each list S_{i} in the set maintains a subset of the elements of M which is sorted in increasing order of the keys. Additionally, each list S_{i} also stores two special keys, denoted as -∞ and +∞ where -∞ is smaller than all possible keys that can be inserted in m and +∞ is greater than all possible keys that can be inserted in M. Additionally, the sublists satisfy the following conditions:

- List S
_{0}contains every possible item that can be stored in the map M (plus -∞ and +∞). - For i = 1, . . . h-1, S
_{i}contains a randomly generated subset of the entries of Si-1 - Lists S
_{h}contains only -∞ and +∞,

**2. Skip List Example**

An example of a skip list is given in Figure 1.0. In this skip lists 10 items are stored in addition to -∞ and +∞. S_{0} is at the bottom of the lists with all the possible elements and as we move to the top of the list from S_{0} to S_{h}, we could see that the number of items gradually reduces such that S_{i+ 1} < S_{i} and also S_{i+1} ⊂ S_{i} (S_{i+1} is a subset of S_{i})

The insertion into a skip list is such that entries into sublist S_{i+1} is randomly chosen from the entries of Si with a probability of 1/2. This means that the number entries of S_{1} is expected to be n/2. Similarly, the number of entries of S_{2} is expected to be n/4 and so on.

Generally, you can expect the number of entries in Si to be 1/2^{i}. This would then mean that the expected height of the skip list would be log n.

We can therefore visualize skip lists as a 2-dimensional set of positions arranged horizontally in levels and vertically in towers. Each level is a sublist S_{i} and each tower is a position for storing similar entries across the lists from bottom to top as can be seen in Figure 1.0. Maybe you can take some time to understand how it works

**3. Skip Lists Traversal**

We can all the positions in skip list by using the following set of operations:

- next(p): returns the position following p on the same level
- prev(p): returns the position preceding p on the same level
- below(p): returns the position directly below p in the same tower
- above(p): returns the position directly above p in the same tower

If however any of the operations mentioned above are carried out and the position does not exist, then the operation returns a null as a result

**4. Skip List Implementation**

You can implement a skip list using a linked structure that allows the four operations outlined above to each take constant time, O(1) given a skip list position p. Such linked list is a collection of doubly-linked list which of length h and are aligned at the towers. The towers are themselves also doubly-linked list.

It is noteworthy that , in Java programming language, there is an implementation of the skip list data structure which is available in the ConcurrentSkipListMap class which provides method for get(), put() and remove, operations which are guaranteed to be performed at O(log n) times.

Finally, The main advantage of the skip list is randomization, which makes them very simple and efficient.

In the next lesson, we would then examine lookup and insertion into linked list.