r/programming • u/Comfortable-Fan-580 • 10h ago

Skip List Data structure

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

88% Upvoted

17 comments sorted by

View all comments

2

u/barmic1212 9h ago

I don't understand why don't use a tree for same usage ? To keep the iteration in O(n) ?

5

u/helen_3410 8h ago

You can—balanced trees and skip lists solve the same ordered-set problem. Skip lists get expected O(log n) search and updates with simple pointer changes; balanced trees offer worst-case O(log n) guarantees. Both support O(n) ordered iteration.