Attributes¶

Classes¶

Functions¶

Module Contents¶

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

__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)¶

__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_search()¶

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¶