A simple implementation of skiplist which keeps track of median of the elements inserted.

skiplist.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 23 12:28:46 2018

@author: Arpit
"""
import random

'''
- Every element in the skiplist has one node.
- A node contains forward pointers for all 
the levels this element goes upto.
- Every node at the lowest level has backward
pointer to point at the previous node.
'''
class Node:
    def __init__(self, key, level):
        self.key = key
        self.forwards = [None] * (level + 1)
        self.backward = None

class SkipList:
    def __init__(self):
        #Header node which contains negative infinity value
        self.header = Node(float("-inf"), 0)
        
        #List of nodes which will need to be updated if a key is inserted
        self.update = []
        
        #Current max level of the skiplist
        self.level = 0
        
        #Keep track of the median node
        self.median = self.header
        
        #Number of keys inserted
        self.keyCnt = 0
    
    def search(self, key):
        node = self.header
        self.update = [None]*(self.level + 1)
        level = self.level
        
        while True:
            #Move forward if the value we are looking for is greater than forward node value
            if node.forwards[level] and key >= node.forwards[level].key:
                node = node.forwards[level]
                
            #Otherwise move down except if it's already on the lowest level
            elif level > 0:
                self.update[level] = node
                level -= 1
            else:
                self.update[0] = node
                break
        
        if node.key == key:
            return True
        else:
            return False

    def insert(self, key):
        #First searches for the key and adds nodes in self.update
        self.search(key)
        
        randLevel = self.getRandomLevel()
        
        '''
        If new random level is higher than the
        maximum level of the skiplist then header
        update is required.
        '''
        if randLevel > self.level:
            for _ in range(randLevel - self.level):
                self.header.forwards.append(None)
                self.update.append(self.header)
            self.level = randLevel
        
        #New node with randLevel levels is created
        newNode = Node(key, randLevel)
        
        #Forward pointers are updated as a new node is inserted
        for i in range(randLevel + 1):
            newNode.forwards[i] = self.update[i].forwards[i]
            self.update[i].forwards[i] = newNode
    
        #Backward pointer on the 0th level is updated as a new node is inserted
        newNode.backward = self.update[0]
        if newNode.forwards[0]:
            newNode.forwards[0].backward = newNode
        
        self.keyCnt += 1
        self.updateMedian(key)
        self.resetUpdate()
        
    def delete(self, key):
        #Remove only if the key exists
        if self.search(key):
            node = self.update[0]
            prev = node.backward
            
            #For zipping up forward pointers after deletion of the node
            for i in range(len(node.forwards)):
                while i >= len(prev.forwards):
                    prev = prev.backward
                
                prev.forwards[i] = node.forwards[i]
            
            #Backward pointer of next node pointed to prev node
            if node.forwards[0]:
                node.forwards[0].backward = node.backward
            
            del node
            self.keyCnt -= 1
            self.updateMedian(key, True)
            self.resetUpdate()

            return True
        else:
            return False
        
    def updateMedian(self, key, deletion=False):
        #update median if insertion happened
        if not deletion:
            if key >= self.median.key and self.keyCnt % 2 != 0:
                self.median = self.median.forwards[0]
            elif key < self.median.key and self.keyCnt % 2 == 0:
                self.median = self.median.backward
                
        #update median if deletion happened
        else:
            if key > self.median.key and self.keyCnt % 2 == 0:
                self.median = self.median.backward
            elif key < self.median.key and self.keyCnt % 2 != 0:
                self.median = self.median.forwards[0]
                
            #corner case where median element is deleted
            elif key == self.median.key:
                print("here")
                if self.keyCnt % 2 == 0:
                    self.median = self.median.backward
                elif self.median == self.update[0]:
                    self.median = self.median.forwards[0]
                
    def getMedian(self):
        if self.keyCnt == 0: return None
        
        if self.keyCnt % 2 == 0:
            return (self.median.key + self.median.forwards[0].key)/2.0
        else:
            return self.median.key
    
    def getRandomLevel(self):
        level = 0
        while random.random() < 0.5:
            level += 1

        return level
    
    def resetUpdate(self):
        self.update = None

    def displayList(self): 
        print("\n*****Skip List******") 
        head = self.header 
        for lvl in reversed(range(self.level+1)): 
            print("Level {}: ".format(lvl), end=" ") 
            node = head.forwards[lvl] 
            while(node is not None): 
                print(node.key, end=" ") 
                node = node.forwards[lvl]
            print("")


s = SkipList()
s.insert(3)
s.insert(30)
s.insert(15)
s.insert(15242)
s.insert(11)
s.insert(9)
s.insert(19)
s.insert(85)
s.insert(135)
s.insert(12)
s.insert(15)
s.insert(152)
s.displayList()
s.getMedian()