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 speeds up inserts and removals too. But this comes at the expense of memory, since the additional elements are proportional (log(n)) to the list length.
For search, trees are great. Regular trees (that is, anything that can be a B-Tree) exhibit...
