Hands-On Data Structures and Algorithms with Rust

Data structures

Algorithms on lists of all kinds almost always exhibit O(n) behavior, since most actions involve shifting or going through other elements. Hence, operations such as insert at or remove from a position, as well as finding elements (when unsorted), are O(n). This is very visible, particularly in linked lists, with only a few exceptions: a dynamic array's element access (O(1)), prepending/appending elements or lists, and splitting lists appending elements in a linked list (O(1)).

Special cases of lists, such as stacks and queues, make use of these exceptions and let a user insert to or remove from only the ends of that list. Skip lists on the other hand employ a tree-like strategy for achieving great search performance, which ...