Check out my first novel, midnight's simulacra!
Skip Lists: Difference between revisions
From dankwiki
No edit summary |
No edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
From [http://www.nist.gov/dads/HTML/skiplist.html NIST]: | From [http://www.nist.gov/dads/HTML/skiplist.html NIST]: | ||
<blockquote>A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).</blockquote> | <blockquote>A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).</blockquote> | ||
MIT OpenCourseware has a [http://academicearth.org/lectures/skip-lists videotaped lecture]. | |||
Latest revision as of 20:43, 4 August 2009
From NIST:
A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).
MIT OpenCourseware has a videotaped lecture.
