added skip lists and a skip list implementation in python
Description
skip lists are another common data structure and adding it will also allow for more opportunities for others to contribute in different languages
added skip lists to read me
added skip list implementation in python
skip_list.py
skip connections made at random
sorted order
removing a node leaves a pseudo dead node
automatically rebuilds with only alive nodes once more than half of the nodes are dead
can be rebuilt whenever desired as well
does not allow for duplicate numbers
methods
reset: reinitialize values of Skip_List, used for rebuilding
status:
reports the total number of unique elements
the number of which that are dead
the number of which are alive
insert:
inserts a new element if the value is not already in list
randomly adds skip connections on new node
updates list head if a skip connection is added that is taller than the current height of the list
find:
if the element is alive
returns the node with the corresponding value at the highest layer
otherwise returns None
remove:
calls find
if node was found then sets it and duplicate skip connection nodes as dead
show_layers:
will print out all nodes in each layer
can specify if you want to print only living nodes, only dead nodes, or both
rebuild:
finds all alive nodes in Skip_List
calls reset
inserts all of the found alive nodes into Skip_List
code verification
the skip_list.py includes a main function which includes trying out different test cases such as inserting a new minimum value, trying to insert a duplicate, removing elements, causing a rebuild and so on.
It also includes inserting 50 arbitrary numbers, then removing 30 of them randomly, and then trying to remove 10 numbers that were never inserted at all.
added skip lists and a skip list implementation in python
Description
skip lists are another common data structure and adding it will also allow for more opportunities for others to contribute in different languages
skip_list.py
methods
code verification
the skip_list.py includes a main function which includes trying out different test cases such as inserting a new minimum value, trying to insert a duplicate, removing elements, causing a rebuild and so on.
It also includes inserting 50 arbitrary numbers, then removing 30 of them randomly, and then trying to remove 10 numbers that were never inserted at all.