MARISSA MOLEJON | OCT2025-1 | Module-Complexity | Sprint 2 | feat/implement skip list - #8

Summary

Implements SkipList in skip_list.py, supporting insert,
__contains__ (the in operator), and to_list, with insert and
contains faster than O(n) as required.

Note: this is marked Optional / Priority Stretch on the issue - opted
to complete it as part of working through the full module.

Design

A skip list keeps multiple "levels" of linked lists stacked on the same
sorted data, where each level up contains roughly half as many elements
as the level below - similar to a book's index letting you skip
straight to a section instead of reading every page.

Each node is assigned a random height at insertion time (a repeated
coin flip, capped at MAX_LEVEL), which is what gives the structure
its logarithmic search time on average, without needing to manually
rebalance anything.

• insert: searches top-down, remembering the last node visited at
  each level (the update array) before dropping down - these are
  exactly the nodes whose forward pointers need to change to splice in
  the new node.
• __contains__: same top-down search, checking for an exact match at
  level 0.
• to_list: a single pass over level 0, which contains every element
  in sorted order.

Testing

Both provided tests pass. Additionally verified locally (not part of
the committed test suite) with a 20,000-element random dataset:

• to_list() output matches Python's sorted() exactly
• 100 present and 100 absent values correctly identified via in
• Timing comparison: a 10x increase in element count (5,000 -> 50,000)
  produced only a ~2.25x increase in contains time, consistent with
  O(log n) rather than O(n) growth

Learning points

• Skip lists trade a guaranteed worst-case bound for a much simpler
  implementation than a balanced tree, at the cost of only offering
  O(log n) average time - an accepted trade-off, the same one hash
  tables make for O(1) average lookup.
• __contains__ (not a custom method name) is required to support
  Python's in operator, which the provided tests rely on via
  assertIn/assertNotIn.
• The update array is the key bookkeeping structure for insert -
  it's what turns the search phase and the splice-in phase into a
  single pass, rather than searching once to find the location and
  then searching again to update pointers.

Checklist

• insert and contains verified faster than O(n)
• to_list returns sorted order
• All tests pass
• No test files modified
• Self-reviewed for readability, naming, and correctness under scale