ABSTRACT
Used By: TaggedSkipList (Section 49.9.8), historical event collection case study (Sections 29.1 and 50.1)
Strengths: Maintains expected logarithmic search cost without any need to restructure. Included within a skip list is a sorted doubly linked list holding all elements in the collection enabling very fast iteration. Removing an element that has been located (either by a search or via a locator) takes expected constant time. A skip list is particularly well suited for a one-dimensional range search. To perform a range search on a skip list, position a tracker at the predecessor of the low end of the range, and then iterate over the collection until reaching an element beyond the desired range.
