A skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n).
Each link of the sparser lists skips over many items of the full list in one step, hence the structure's name. These forward links may be added in a randomized way with a geometric / negative binomial distribution. Insert, search and delete operations are performed in logarithmic expected time. The links may also be added in a non-probabilistic way so as to guarantee amortized (rather than merely expected) logarithmic cost.
Read more about Skip List: Description, History, Usages
Famous quotes containing the words skip and/or list:
“Grown up, and that is a terribly hard thing to do. It is much easier to skip it and go from one childhood to another.”
—F. Scott Fitzgerald (18961940)
“Every morning I woke in dread, waiting for the day nurse to go on her rounds and announce from the list of names in her hand whether or not I was for shock treatment, the new and fashionable means of quieting people and of making them realize that orders are to be obeyed and floors are to be polished without anyone protesting and faces are to be made to be fixed into smiles and weeping is a crime.”
—Janet Frame (b. 1924)