You need to login before you can make any post submission.

Add New Chapter
## Tutorial

# Skip List

###### What is Skip List ?

###### Why Skip List ?

#### Express and Normal Lane

###### Exstimating Complexity:

#### Doing Better than O(√n) : Increase Levels

### Skip List Insertion

###### Deciding nodes level while Insertion:

###### Implementation

###### Complexity:

### Skip List Deletion

- Invented around
**1990**by**Bill Pugh**. - Efficient Dynamic Search Structure: Expected search time is O(log n)
- Randomized data structure: Use random coin flips to build the data structure

- Worst case search time for a
**sorted linked list**is**O(n)**as we can only linearly traverse the list and cannot skip nodes while searching. - For a
**Balanced Binary Search Tree**, we skip almost half of the nodes after one comparison with root and hence**O(logn)**. - For a
**sorted array**, we have random access and we can apply**Binary Search**on arrays and hence**O(logn)**. - We can do similar things by augmenting list as Skip List.

- We will make use of normal and express lane for understanding this concept.
16 nodes Normal lane with 4 nodes Express Lane*Example:*

- The worst case time complexity is number of nodes on express lane plus number of nodes in a segment (b/w 2 express lane nodes).
- Here n normal nodes and √n express nodes.
**Average time complexity:**O(√n)**Auxilliary Space:**O(√n)

- The time complexity of skip lists can be reduced further by adding more layers.
- In fact, the time complexity of search, insert and delete can become
**O(Logn)**in average case with**O(n)**extra space.

- Each element in the list is represented by a node, the level of the node is chosen randomly while insertion in the list.
**Level does not depend on the number of elements in the node.**- The level for node is decided by the following algorithm:

```
randomLevel()
lvl := 1
//random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl
```

**MaxLevel**is the upper bound on number of levels in the skip list and can be determined by**L(N) = log**._{p/2}N- Above algorithm assure that random level will never be greater than MaxLevel.
- Here
**p**is the fraction of the nodes with level**i**pointers also having level**i+1**pointers and N is the number of nodes in the list.

```
from random import random
class Node:
def __init__(self, key, level):
self.key = key
self.next = [None]*(level+1)
class SkipList:
def __init__(self, max_level, P):
# Maximum level for this skip list
self.max_level = max_level
# P is the fraction of the nodes with level i references also having level i+1 references
self.P = P
# create head node and initialize key to -1
self.head = Node(-1, max_level)
# temp level of skip list
self.level = 0
def get_random_level(self):
lvl = 0
while random() < self.P and lvl < self.max_level:
lvl += 1
return lvl
def insert_key(self, key):
# create update array and initialize it
update = [None]*(self.max_level+1)
temp = self.head
# start from highest level of skip list move the temp reference next while key
# is greater than key of node next to temp, Otherwise inserted temp in update and
# move one level down and continue search.
for i in range(self.level, -1, -1):
while temp.next[i] and temp.next[i].key < key:
temp = temp.next[i]
update[i] = temp
# reached level 0, now get the node next to temp, need to insert b/w temp and next_node
next_node = temp.next[0]
# if next_node is NULL that means we have reached to end of the level or
# if next_node's key != key to insert that means we have to insert node between update[0] and next_node
if next_node == None or next_node.key != key:
# Generate a random level for node
random_level = self.get_random_level()
# If random level is greater than list's next_node level
# (node with highest level inserted in list so far),
# initialize update value with reference to head for further use
if random_level > self.level:
for i in range(self.level+1, random_level+1):
update[i] = self.head
self.level = random_level
# create new node with random level generated
new_node = Node(key, random_level)
# insert node by rearranging references
for i in range(random_level+1):
new_node.next[i] = update[i].next[i]
update[i].next[i] = new_node
print(key, end=" ")
def display_list(self):
print("\n\nFinal Skip List Level wise:")
head = self.head
for lvl in range(self.level+1):
print("Level - [{}]: ".format(lvl), end=" ")
node = head.next[lvl]
while(node != None):
print(node.key, end=" ")
node = node.next[lvl]
print()
# Driver Program
print("Skip List Example:")
lst = SkipList(3, 0.5)
print("Insert Keys: ", end=" ")
lst.insert_key(3)
lst.insert_key(6)
lst.insert_key(7)
lst.insert_key(9)
lst.insert_key(12)
lst.insert_key(19)
lst.insert_key(17)
lst.insert_key(26)
lst.insert_key(21)
lst.insert_key(25)
lst.display_list()
```

**Output:**

**Time:**Search - O(logn) and Insert - O(logn)**Auxilliary Space:**O(logn)