Data Structures: A learning journey
summary
Builds a skip list implemented skip list in Python from scratch, starting with a custom linked list and about ~70–80 methods across node, iterator/position and container classes. Uses coin flips for probabilistic promotion, dunder methods, recursion and exceptions. Claims average search time search average O(log n) vs linked list O(n). Tests are ad hoc so methods mostly work for small lists but printing and some behaviors break past ~10 elements. Also implements a hashet for practice and considers a red black binary tree next.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:02Why this talk
- 3:15Skip list discovery
- 4:58Linked lists explained
- 7:04Skip lists and fast lanes
- 8:51Skip lists and binary search
- 10:36Big O notation explained
- 13:05Coding skip list from scratch
- 17:41Hash sets in Python
- 19:29Skip list challenges
- 21:37Python dunder methods
- 23:03Conclusion
- 24:47Audience questions and answers
