A Practical Guide to Data Structures and Algorithms using Java

OrderedCollection

Chapter 38

Skip List Data Structure

AbstractCollection<E> implements Collection<E>

↑

SkipList<E> implements OrderedCollection<E>, Tracked<E>

Uses: Java array and references

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 ...