Class SkipList<K, V>

Type Parameters

  • K

  • V

Constructors

constructor

Accessors

first head last level maxLevel probability

Methods

_randomLevel add delete get has higher lower

Constructors

constructor

  • new SkipList<K, V>(elements?, options?): SkipList<K, V>

  • The constructor function initializes a SkipLinkedList object with optional options and elements.

    Type Parameters

    • K

    • V

    Parameters

    • elements: Iterable<[K, V]> = []

      The elements parameter is an iterable containing key-value pairs [K, V]. It is used to initialize the SkipLinkedList with the given key-value pairs. If no elements are provided, the SkipLinkedList will be empty.

    • Optional options: SkipLinkedListOptions

      The options parameter is an optional object that can contain two properties:

    Returns SkipList<K, V>

Accessors

first

  • get first(): undefined | V

  • Time Complexity: O(1) Space Complexity: O(1)

    Get the value of the first element (the smallest element) in the Skip List.

    Returns undefined | V

    The value of the first element, or undefined if the Skip List is empty.

head

last

  • get last(): undefined | V

  • Time Complexity: O(log n) Space Complexity: O(1)

    Get the value of the last element (the largest element) in the Skip List.

    Returns undefined | V

    The value of the last element, or undefined if the Skip List is empty.

level

  • get level(): number

  • The function returns the value of the protected variable _level.

    Returns number

    The level property of the object.

maxLevel

  • get maxLevel(): number

  • The function returns the maximum level.

    Returns number

    The value of the variable _maxLevel is being returned.

probability

  • get probability(): number

  • The function returns the probability value.

    Returns number

    The probability value stored in the protected variable _probability is being returned.

Methods

Protected _randomLevel

  • _randomLevel(): number

  • Time Complexity: O(maxLevel) Space Complexity: O(1)

    The function "_randomLevel" generates a random level based on a given probability and maximum level.

    Returns number

    the level, which is a number.

add

  • add(key, value): void

  • Time Complexity: O(log n) Space Complexity: O(1)

    The add function adds a new node with a given key and value to a Skip List data structure.

    Parameters

    • key: K

      The key parameter represents the key of the node that needs to be added to the skip list.

    • value: V

      The "value" parameter represents the value associated with the key that is being added to the Skip List.

    Returns void

delete

  • delete(key): boolean

  • Time Complexity: O(log n) Space Complexity: O(1)

    The delete function removes a node with a specific key from a Skip List data structure.

    Parameters

    • key: K

      The key parameter represents the key of the node that needs to be removed from the skip list.

    Returns boolean

    The delete method returns a boolean value. It returns true if the key was successfully removed from the skip list, and false if the key was not found in the skip list.

get

  • get(key): undefined | V

  • Time Complexity: O(log n) Space Complexity: O(1)

    The function get retrieves the value associated with a given key from a skip list data structure.

    Parameters

    • key: K

      The key parameter is the key of the element that we want to retrieve from the data structure.

    Returns undefined | V

    The method get(key: K) returns the value associated with the given key if it exists in the data structure, otherwise it returns undefined.

has

  • has(key): boolean

  • The function checks if a key exists in a data structure.

    Parameters

    • key: K

      The parameter "key" is of type K, which represents the type of the key being checked.

    Returns boolean

    a boolean value.

higher

  • higher(key): undefined | V

  • Time Complexity: O(log n) Space Complexity: O(1)

    Get the value of the first element in the Skip List that is greater than the given key.

    Parameters

    • key: K

      the given key.

    Returns undefined | V

    The value of the first element greater than the given key, or undefined if there is no such element.

lower

  • lower(key): undefined | V

  • Time Complexity: O(log n) Space Complexity: O(1)

    Get the value of the last element in the Skip List that is less than the given key.

    Parameters

    • key: K

      the given key.

    Returns undefined | V

    The value of the last element less than the given key, or undefined if there is no such element.

Settings

Member Visibility

Theme

On This Page

Generated using TypeDoc