data_structures.linked_list.skip_list

Based on “Skip Lists: A Probabilistic Alternative to Balanced Trees” by William Pugh https://epaperpress.com/sortsearch/download/skiplist.pdf

Attributes

KT

VT

Classes

Node

SkipList

Functions

main()

pytests()

test_delete_doesnt_leave_dead_nodes()

test_delete_removes_only_given_key()

test_deleted_items_are_not_founded_by_find_method()

test_deleting_item_from_empty_list_do_nothing()

test_insert()

test_insert_overrides_existing_value()

test_iter_always_yields_sorted_values()

test_search()

test_searching_empty_list_returns_none()

Module Contents

class data_structures.linked_list.skip_list.Node(key: KT | str = 'root', value: VT | None = None)

Bases: Generic[KT, VT]

__repr__() → str
Returns:

Visual representation of Node

>>> node = Node("Key", 2)
>>> repr(node)
'Node(Key: 2)'
forward: list[Node[KT, VT]] = []
key = 'root'
property level: int
Returns:

Number of forward references

>>> node = Node("Key", 2)
>>> node.level
0
>>> node.forward.append(Node("Key2", 4))
>>> node.level
1
>>> node.forward.append(Node("Key3", 6))
>>> node.level
2
value = None
class data_structures.linked_list.skip_list.SkipList(p: float = 0.5, max_level: int = 16)

Bases: Generic[KT, VT]

__iter__()
__str__() → str
Returns:

Visual representation of SkipList

>>> skip_list = SkipList()
>>> print(skip_list)
SkipList(level=0)
>>> skip_list.insert("Key1", "Value")
>>> print(skip_list) 
SkipList(level=...
[root]--...
[Key1]--Key1...
None    *...
>>> skip_list.insert("Key2", "OtherValue")
>>> print(skip_list) 
SkipList(level=...
[root]--...
[Key1]--Key1...
[Key2]--Key2...
None    *...
_locate_node(key) → tuple[Node[KT, VT] | None, list[Node[KT, VT]]]
Parameters:

key – Searched key,

Returns:

Tuple with searched node (or None if given key is not present) and list of nodes that refer (if key is present) of should refer to given node.

delete(key: KT)
Parameters:

key – Key to remove from list.

>>> skip_list = SkipList()
>>> skip_list.insert(2, "Two")
>>> skip_list.insert(1, "One")
>>> skip_list.insert(3, "Three")
>>> list(skip_list)
[1, 2, 3]
>>> skip_list.delete(2)
>>> list(skip_list)
[1, 3]
find(key: VT) → VT | None
Parameters:

key – Search key.

Returns:

Value associated with given key or None if given key is not present.

>>> skip_list = SkipList()
>>> skip_list.find(2)
>>> skip_list.insert(2, "Two")
>>> skip_list.find(2)
'Two'
>>> skip_list.insert(2, "Three")
>>> skip_list.find(2)
'Three'
insert(key: KT, value: VT)
Parameters:

  • key – Key to insert.

  • value – Value associated with given key.

>>> skip_list = SkipList()
>>> skip_list.insert(2, "Two")
>>> skip_list.find(2)
'Two'
>>> list(skip_list)
[2]
random_level() → int
Returns:

Random level from [1, self.max_level] interval. Higher values are less likely.

head: Node[KT, VT]
level = 0
max_level = 16
p = 0.5
data_structures.linked_list.skip_list.main()
>>> pytests()
data_structures.linked_list.skip_list.pytests()
data_structures.linked_list.skip_list.test_delete_doesnt_leave_dead_nodes()
data_structures.linked_list.skip_list.test_delete_removes_only_given_key()
data_structures.linked_list.skip_list.test_deleted_items_are_not_founded_by_find_method()
data_structures.linked_list.skip_list.test_deleting_item_from_empty_list_do_nothing()
data_structures.linked_list.skip_list.test_insert()
data_structures.linked_list.skip_list.test_insert_overrides_existing_value()
data_structures.linked_list.skip_list.test_iter_always_yields_sorted_values()
data_structures.linked_list.skip_list.test_searching_empty_list_returns_none()
data_structures.linked_list.skip_list.KT
data_structures.linked_list.skip_list.VT