Hands-On Data Structures and Algorithms with Rust

The list

Other than a simple pointer to the head, the list best stores the length as well as the maximum level that elements can have. This user-supplied parameter is critical, since if it's chosen too low, searching will approximate the search performance of a singly linked list (O(n)).

In contrast, choosing a maximum level that is too high will also result in an uneven distribution that could see as many vertical (levels down) as horizontal iterations (O(n + h) ), none of which are good. The Big O notation (O(n) and so on) will be discussed in Chapter 8, Algorithm Evaluation.

Consequently, this parameter has to be set to somewhat reflect the future size of the list and the highest level only contains two or three nodes at most:

#[derive(Clone)] ...