Skip List¶
A skip list is an awesome linear data structures which consists of a series of Linked List objects, each linked list stores a subset of items sorted by increasing values plus one setntinel value denoted by -∞ which is smaller than every possible value that can be inserted. The really interesting part about skip list is that it supports searching for values in time-complexity of O(log(n)) which is considered faster than most linear data structures.
The following is a simple skip list containing the first seven number from the Fibbonacci series which are: [0, 1, 1, 2, 3, 5, 8]
┌────┐ ┌───┐ ┌───┐
| -∞ │⟶| 0 │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 8 │⟶
├────┤ ├───┤ ┌───┐ ├───┤
| -∞ │⟶| 0 │⟶| 1 │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 8 │⟶
├────┤ ├───┤ ├───┤ ┌───┐ ┌───┐ ┌───┐ ├───┤
| -∞ │⟶| 0 │⟶| 1 │⟶| 2 │⟶| 3 │⟶| 5 │⟶| 8 │⟶
└────┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
In the above skip list, you can see the following properties:
- The skip list consists of multiple levels or Linked List objects. The number of levels is called “height”. So, the height of this skip list is 3.
- The first number in the skip list is our -∞ setntinel value.
- All values are numbers and they are sorted in ascending-manner.
- There are no repeated values.
- There are some numbers that are stored once and there are some numbers that are stored multiple time.
Intuitively, the lists are set up so that the lower linked lists contain more items of the higher ones. Inserting an item in more than one linked list is chosen randomly with probability 1/2. That is, like, we “flip a coin” for each item in the skip list. Thus, we expect the lowest linked list, at height=0 to have n items. And the linked list at height=2 to have about n/2 items, and the one above it to have about n/4 items. In other words, we expect the height of the skip list to be about log(n).
The -∞ setntinel value is put in the SkipList() as a convention. So, it doesn’t count as an element in the SkipList(). In other words, the zeroths element in the above skip list is 0 not -∞.
⏱ Time-Complexity¶
The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:
- n is the number of elements currently in the skip list.
- k is the value of a parameter.
- h is the height of the skip list.
| Method | Description | Worst-case | Optimal |
|---|---|---|---|
| is_empty() | Checks if the skip list is empty. | O(1) | O(1) |
| __len__() | Returns the number of skip nodes. | O(1) | O(1) |
| __repr__() | Represents the skip list as a string. | O(n*h) | O(n*h) |
| __iter__() | Iterates over the skip list. | O(n) | O(n) |
| __contains__() | Checks the existence of the given item. | O(log(n)) | O(log(n)) |
| __getitem__() | Returns the element at a certain index. | O(k) | O(k) |
| __delitem__() | Deletes the value at the given index. | O(k) | O(k) |
| insert() | Adds the given item to the instance. | O(k) | O(k) |
| remove() | Removes the given value if found. | O(log(n)) | O(log(n)) |
| clear() | Clears the whole skip list. | O(1) | O(1) |
| to_list() | Converts the skip list to a normal list. | O(n) | O(n) |
☕️ API¶
Here are all of the public methods that can be used with SkipList() objects:
-
class
extra.lists.skip_list.SkipList(iterable=None)¶ A skip list is an awesome linear data structures which consists of a series of Linked List objects, each linked list stores a subset of items sorted by increasing values plus one setntinel value denoted by -∞ which is smaller than every possible value that can be inserted. The really interesting part about skip list is that it supports searching for values in time-complexity of O(log(n)) which is considered faster than most linear data structures.
-
__contains__(value)¶ Checks if the given value exists in the SkipList() instance in time- complexity of O(log(n)) where n is the total number of elements in the SkipList() instance.
Parameters: value (Object) – The value to be searched for in the SkipList() instance. Returns: True if the given value exists in the SkipList() instance, and False otherwise. Return type: bool Raises: ValueError: – If the given item is None. Examples
>>> sl = SkipList([1, 3, 5]) >>> 1 in sl True >>> 0 in sl False >>> "hello" in sl False
-
__delitem__(idx)¶ Removes node at a given index at the SkipList() instance.
Parameters: idx (int) – An integer pointing to the index where the node that should be removed.
Raises: - TypeError: – If the given index isn’t int.
- IndexError: – This happens in one of the following cases:
- If the given index is negative.
- If the given index is out of the SkipList() boundaries.
- if the given index is a slice object.
Example
>>> import random; random.seed(1) >>> sl = SkipList([4, 3, 1, 5]) >>> sl ┌────┐ ┌───┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 3 │⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ ├───┤ ┌───┐ | -∞ │⟶| 1 │⟶| 3 │⟶| 4 │⟶| 5 │⟶ └────┘ └───┘ └───┘ └───┘ └───┘ >>> del sl[2] >>> sl ┌────┐ ┌───┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 3 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ ┌───┐ | -∞ │⟶| 1 │⟶| 3 │⟶| 5 │⟶ └────┘ └───┘ └───┘ └───┘ >>> del sl[10] IndexError: Can't find any element at the given index!!
Note
In the previuos example, the top level was deleted when we removed 4 since it was empty after removal.
-
__getitem__(idx)¶ Retrieves the element at the given index in time-complexity of O(k) where k is the given index. The given index is a zero-based int. This method doesn’t support negative indexing and doesn’t support slice objects either.
Parameters: idx (int) – The index to be used to retrieve the stored value from the SkipList() instance.
Returns: The value at this index inside the SkipList() instance.
Return type: int or float
Raises: - TypeError: – If the given index isn’t int.
- IndexError: – This happens in one of the following cases:
- If the given index is negative.
- if the given index is a slice object.
- If the given index is out of the SkipList() boundaries.
Examples
>>> sl = SkipList([4, 3, 1, 5, 2]) >>> sl[0] 1 >>> sl[4] 5 >>> sl[10] IndexError: Can't find any element at the given index!! >>> sl[-2] IndexError: Negative indexing isn't supported with this functinoality!! >>> sl[2:] IndexError: Slice indexing isn't supported with this functinoality!!
Note
The -∞ setntinel value is put in the SkipList() as a convention. So, it doesn’t count as an element of the SkipList(). In other words, the zeroths element in the above skip list is 0 not -∞.
-
__init__(iterable=None)¶ Initializes a SkipList() instance using an optional iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.
Parameters: iterable (iterable, optional) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.
Raises: - TypeError: – It can be raised in three cases
- In case the given object isn’t iterable.
- If one of the elements in the iterable is an Extra object.
- If one of the elements in the iterable is NOT a number.
- ValueError: – If one of the iterable elements is None.
Note
Inserting values into different levels in the skip list is completely random. So, running the following example will return different values each time you run it. So, in order to obtain the same result as before you need to set random.seed(1) before running any of the previous example.
Examples
>>> import random; random.seed(1) >>> sl = SkipList([10, -5, 7, 9]) >>> sl ┌────┐ ┌────┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 10 │⟶ ├────┤ ┌────┐ ├────┤ | -∞ │⟶| -5 │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 10 │⟶ ├────┤ ├────┤ ┌───┐ ┌───┐ ├────┤ | -∞ │⟶| -5 │⟶| 7 │⟶| 9 │⟶| 10 │⟶ └────┘ └────┘ └───┘ └───┘ └────┘
Using an iterable object with None as one of its elements will raise ValueError
>>> sl = SkipList([2, None]) ValueError: Can't use `None` as an element within `extra.SkipList()`!!
Using a non-iterable object will raise TypeError
>>> sl = SkipList(2) TypeError: The given object isn't iterable!!
Using nested SkipList objects will raise TypeError as well
>>> sl_1 = SkipList([1]) >>> sl_2 = SkipList([1, sl_1]) TypeError: Can't create `extra.SkipList()` using `extra.SkipList()`!!
-
__iter__()¶ Iterates over the SkipList() instance and returns a generator in time-complexity of O(n) where n is the number of elements in the SkipList() instance.
Returns: The value of each node in the instance. Return type: generator Examples
>>> sl = SkipList([3, 1, 2]) >>> for item in sl: ... print(item) 1 2 3
-
__len__()¶ Gets the length of the SkipList() in time-complexity of O(1).
Returns: The length of the SkipList() instance. By Length, I mean the number of nodes of in the instance. Return type: int Examples
>>> sl = SkipList() >>> len(sl) 0 >>> sl = SkipList((2, 5, 0)) >>> len(sl) 3
-
__repr__()¶ Represents the linked list as a string. The time-complexity of this method is O(n*h) where n is the number of nodes in the SkipList() and h is the height of the SkipList().
Returns: The string-representation of the SkipList() instance. Return type: str Example
>>> import random; random.seed(1) >>> sl = SkipList([20, 77, 10, 6, 2]) >>> sl ┌────┐ ┌────┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 20 │⟶⟶⟶⟶⟶⟶⟶⟶ ├────┤ ├────┤ ┌────┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 20 │⟶| 77 │⟶ ├────┤ ┌───┐ ┌───┐ ┌────┐ ├────┤ ├────┤ | -∞ │⟶| 2 │⟶| 6 │⟶| 10 │⟶| 20 │⟶| 77 │⟶ └────┘ └───┘ └───┘ └────┘ └────┘ └────┘
-
clear()¶ Removes all nodes within the SkipList() in constant time.
Example
>>> import random; random.seed(1) >>> sl = SkipList([4, 3, 1, 5]) >>> sl ┌────┐ ┌───┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 3 │⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ ├───┤ ┌───┐ | -∞ │⟶| 1 │⟶| 3 │⟶| 4 │⟶| 5 │⟶ └────┘ └───┘ └───┘ └───┘ └───┘ >>> sl.clear() >>> sl.is_empty() True >>> sl ┌────┐ | -∞ │⟶ └────┘
-
get_height()¶ Gets the height of the SkipNode() instance. SkipNode() height is the number of levels where each level is a standalone LinkedList() object.
Returns: A positive integer representing the height of the instance. Return type: int Example
>>> import random; random.seed(1) >>> sl = SkipList([20, 77, 10, 6, 2]) >>> sl.get_height() 3
-
insert(value)¶ Insertd a value to the SkipList() instance in time-complexity of O(log(n)) where n is the number of elements in the SkipList().
Parameters: value (int or float) – The number to be inserted in the SkipList() instance. Raises: TypeError: If the given value isn’t a number. Example
>>> import random; random.seed(1) >>> sl = SkipList([2, 1, 3, 4, 5]) >>> sl.insert(10) >>> sl ┌────┐ ┌───┐ ┌────┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 2 │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 10 │⟶ ├────┤ ┌───┐ ├───┤ ├────┤ | -∞ │⟶| 1 │⟶| 2 │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 10 │⟶ ├────┤ ├───┤ ├───┤ ┌───┐ ┌───┐ ┌───┐ ├────┤ | -∞ │⟶| 1 │⟶| 2 │⟶| 3 │⟶| 4 │⟶| 5 │⟶| 10 │⟶ └────┘ └───┘ └───┘ └───┘ └───┘ └───┘ └────┘ >>> sl.insert("hi") TypeError: `extra.SkipList()` supports only numbers!!
Note
Inserting values into different levels in the skip list is completely random. So, running the previous example will return different values each time you run it. So, in order to obtain the same result as before you need to set random.seed(1) before running any of the previous example.
-
is_empty()¶ Checks if the SkipList() instance is empty or not in constant time.
Returns: A boolean flag showing if the SkipList() instance is empty or not. True shows that this instance is empty and False shows it’s not empty. Return type: bool Example
>>> sl = SkipList() >>> sl.is_empty() True >>> sl.insert(5) >>> sl.is_empty() False
-
remove(value)¶ Removes node whose value equal to the given value.
Parameters: value (int or float) – The value to be removed from the SkipList() instance. Example
>>> import random; random.seed(1) >>> sl = SkipList([4, 3, 1, 5]) >>> sl ┌────┐ ┌───┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 3 │⟶| 4 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ ├───┤ ┌───┐ | -∞ │⟶| 1 │⟶| 3 │⟶| 4 │⟶| 5 │⟶ └────┘ └───┘ └───┘ └───┘ └───┘ >>> sl.remove(10) #does nothing >>> sl.remove(4) >>> sl ┌────┐ ┌───┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶| 3 │⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌───┐ ├───┤ ┌───┐ | -∞ │⟶| 1 │⟶| 3 │⟶| 5 │⟶ └────┘ └───┘ └───┘ └───┘
Note
In the previuos example, the top level was deleted when we removed 4 since it was empty after removal.
-
to_list()¶ Converts the SkipList() instance to a list in time-complexity of O(n) where n is the number of elements in the instance.
Returns: A list object containing the same elements as the SkipList() instance. Return type: list Example
>>> import random; random.seed(1) >>> sl = SkipList() >>> sl.insert(20) >>> sl.insert(10) >>> sl.insert(30) >>> sl ┌────┐ ┌────┐ | -∞ │⟶⟶⟶⟶⟶⟶⟶⟶| 20 │⟶⟶⟶⟶⟶⟶⟶⟶ ├────┤ ┌────┐ ├────┤ | -∞ │⟶| 10 │⟶| 20 │⟶⟶⟶⟶⟶⟶⟶⟶ ├────┤ ├────┤ ├────┤ ┌────┐ | -∞ │⟶| 10 │⟶| 20 │⟶| 30 │⟶ └────┘ └────┘ └────┘ └────┘ >>> sl.to_list() [10, 20, 30]
-
