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:
“We are playing with fire when we skip the years of three, four, and five to hurry children into being age six.... Every child has a right to his fifth year of life, his fourth year, his third year. He has a right to live each year with joy and self-fulfillment. No one should ever claim the power to make a child mortgage his today for the sake of tomorrow.”
—James L. Hymes, Jr. (20th century)
“I am opposed to writing about the private lives of living authors and psychoanalyzing them while they are alive. Criticism is getting all mixed up with a combination of the Junior F.B.I.- men, discards from Freud and Jung and a sort of Columnist peep- hole and missing laundry list school.... Every young English professor sees gold in them dirty sheets now. Imagine what they can do with the soiled sheets of four legal beds by the same writer and you can see why their tongues are slavering.”
—Ernest Hemingway (1899–1961)