https://nick-black.com/dankwiki/index.php?action=history&feed=atom&title=Skip_ListsSkip Lists - revision history2026-07-11T16:57:30ZRevision history for this page on the wikiMediaWiki 1.46.0https://nick-black.com/dankwiki/index.php?title=Skip_Lists&diff=806&oldid=prevDank at 20:43, 4 August 20092009-08-04T20:43:07Z<p></p>
<table style="background-color: #fff; color: #202122;" data-mw-interface="">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:43, 4 August 2009</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>From [http://www.nist.gov/dads/HTML/skiplist.html NIST]:</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>From [http://www.nist.gov/dads/HTML/skiplist.html NIST]:</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><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></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><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></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">MIT OpenCourseware has a [http://academicearth.org/lectures/skip-lists videotaped lecture].</ins></div></td></tr>
<!-- diff cache key wikidb:diff:1.41:old-143:rev-806:php=table -->
</table>Dankhttps://nick-black.com/dankwiki/index.php?title=Skip_Lists&diff=143&oldid=prevWikiSysop: 1 revision2009-01-28T07:32:16Z<p>1 revision</p>
<table style="background-color: #fff; color: #202122;" data-mw-interface="">
<tr class="diff-title" lang="en">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:32, 28 January 2009</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>WikiSysophttps://nick-black.com/dankwiki/index.php?title=Skip_Lists&diff=142&oldid=prevDank at 23:46, 27 December 20082008-12-27T23:46:54Z<p></p>
<p><b>New page</b></p><div>From [http://www.nist.gov/dads/HTML/skiplist.html NIST]:<br />
<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></div>Dank