CODEWITHSUNDEEP
pythonpython-3.xdata-structuresskip-lists
NX27
NX27

Reputation: 1

Skip list implementation python

im trying to implement the data structure skiplist in python but am a little stuck, specifically with how to implement insertion & print functions (to visualize it). Any help, tips, explanations are super welcome, as i am a beginner. I understand the data structure, and wanna understand the implementation as well. Idea was to print lvls like this lvl 0 -inf, 1, 2, 3, inf lvl 1 -inf, 2, inf lvl 2 -inf, inf

Thanks !

import math
import random as rnd


# node class of skiplist, as given by instructor should have pointers to: pred, next, down

class node:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.next = None
        self.pred = None
        self.down = None


class skipList:
    def __init__(self):
        self.head = node(-math.inf)
        self.tail = node(math.inf)
        self.head.next = self.tail
        self.tail.pred = self.head
        self.length = 0
        self.height = 1


def createLevel(self):  # creates new frame lvl with only -inf/inf as nodes
    newHead = node(- math.inf)
    newTail = node(math.inf)
    newHead.next = newTail
    newTail.pred = newHead
    newHead.down = self.head
    newTail.down = self.tail
    self.head = newHead
    self.tail = newTail


def newLevel(self, levels):
    if levels >= self.height:
        self.height += 1
        self.createLevel()


def coinFlip(self):  # see how many lvls item to be inserted in
    x = rnd.randint(0, 1)
    return x


def search(self, key):  # search returns stack of nodes traversed to reach k
    q = []
    current_node = self.head
    while current_node.down != None:
        current_node = current_node.down
        while current_node.next.key <= key:
            current_node = current_node.next
        q.append(current_node.key)
    return q


def put(self, key, value):
    q = self.search(key)
    current_node = q.pop()  # if k exists, insert new value in k
    if current_node.key == key:
        current_node.value = value
        return
    else:  # else create k after current_node
        while self.coinFlip() == 1:  # check for how many levels
            if q == []:  # key is not in the skiplist, or skiplist empty
        # stuck here. idea: createLevel(), create new_node in levels
        # (unsure how to achieve this for all lvls at once/individually?
        # adjust pointers


def printSkip(self):  # or is it best to use the __str__ method, if so how?
    xs = []
    current_node = self.head
    for level in range(self.height):
        print("level", level)
        while current_node.next != None:
            xs.append(current_node.key)
            current_node = current_node.next
    print(xs)

so far I can only add to level 0, but when i want to add a new level with the createLevel() then the element doesnt get "put" in the skiplist, let alone adding an element on several levels..

On the print function, I've tried with 2 for loops, as well as a for + while loop (one to determine level and then append all keys before carrying on to next level) but ive only achieved to get level 0 printed and the level heights...

Upvotes: 0

Views: 916

Answers (1)

Vishwajeet kumar
Vishwajeet kumar

Reputation: 1

import math import random as rnd

#node class of skiplist, as given by instructor should have pointers to: pred, next, down 

class node:                        
    def __init__(self, key, value = None):
        self.key = key
        self.value = value 
        self.next = None 
        self.pred = None
        self.down = None 

class skipList:                
    def __init__(self):
        self.head = node(-math.inf)
        self.tail = node(math.inf)
        self.head.next = self.tail 
        self.tail.pred = self.head 
        self.length = 0
        self.height = 1

def createLevel(self):      #creates new frame lvl with only -inf/inf as nodes
    newHead = node(- math.inf)
    newTail = node(math.inf)
    newHead.next = newTail
    newTail.pred = newHead
    newHead.down = self.head
    newTail.down = self.tail 
    self.head = newHead
    self.tail = newTail

def newLevel(self, levels):
    if levels >= self.height :         
        self.height += 1
        self.createLevel()

def coinFlip(self):             #see how many lvls item to be inserted in
    x = rnd.randint(0, 1)
    return x 

def search(self, key):    # search returns stack of nodes traversed to reach k 
    q = [] 
    current_node = self.head 
    while current_node.down != None :
        current_node = current_node.down
        while current_node.next.key

Upvotes: -2

Related Questions