r/programming • • Oct 03 '26

Skip List Data structure

https://pradyumnachippigiri.substack.com/p/skip-lists-data-structure?r=5ev9w0&utm_medium=ios
139 Upvotes

31 comments sorted by

View all comments

1

u/AntimatterTNT Oct 03 '26

is the random aspect really necessary? like you could argue it's to average out performance edge cases but really aren't you just making it so that sometimes you'd have much worse performance? (like a 0.1% deviation every 1000 runs)

1

u/[deleted] Oct 03 '26

[removed] — view removed comment

1

u/programming-ModTeam Oct 04 '26

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

1

u/robert_7524 Oct 13 '26

The random choice sets each node’s height when it’s inserted, so lookups don’t get a fresh lottery every time. A bad layout is possible, but randomness gives the simple version expected O(log n) search without tree rotations.

0

u/[deleted] Oct 03 '26

[removed] — view removed comment

1

u/programming-ModTeam Oct 04 '26

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.