Skip Lists

This is a short and simple introduction to skip lists.

0:00 Motivation
2:26 Perfect skip lists
3:11 Searching in a skip list
4:27 Analysis of perfect skip list
5:56 Randomization
7:20 Inserting into a skip list
8:11 Analysis
8:32 Expected size of a skip list
10:57 Expected length of the search path
11:37 Backwards analysis
14:34 Wrap-Up

[orelyosef]

Facinating data structure really, the combination of the benefits of the 2 most popular structures, an array and a linked list.

[Abhay.Bhandari]

Its a great lecture. You have taught it so well and no one else have taught like this. Teaching is an art and you are the great artist.

[evasionlan]

easy to understand and also deep enough, quiz are great too. Thank you!

[imumamaheswaran]

I was reading about redis indexing and came across skiplist. Never heard of it before. Thanks for the beautiful explanation! Subscribed to the channel

[axlrose]

You're amazing! I finally understood everything involving this interesting DS. Thank you for explaining the intuition behind every property and behaviour!

[vibhavadayar]

Exceptionally intuitive video. Thank you!

[spartanzarazua]

Too much thanks a very good explanation and also with animation. There are 15 minutes well invested.
A new subscriber.

[cathynest]

Saved me on exam today!!! Explanation is amazing

[timyturner]

Danke sehr mr buchin. incredible video and presentation

[aldrinseanpereira]

I just found this channel by searching for amortised analysis for my college course... your style of presenting the subject by slides and the teaching is a life-saver! THANK YOU!!!
i really hope you gain more views and subs so all students can benefit

[TheAdaya]

great video!! it really helped me studying for a test

[williamikennanwosu]

Nice and clear video, great explanation!

[retiksingh]

Fantastic work man!! Absolutely spot on. Exactly what i needed

[empireempire]

I absolutely love this, never heard of them and this looks great : O

[ayeyo]

6:55 looks like it was actually heads but you just decided to say it was tails for the sake of the lesson 😂
7:12 not even looking at the coin anymore 😂😂
thanks for the great video !

[manuelpagliuca]

Thank you for this video, really good explanation

[Jarreddesigns]

Thank you for this video, cleared up all my confusion

[vctorroferz]

Amazing video really good explanation ! Thanks so much

[romangavrilovich]

Hi, thanks for explanation, but it didn’t get the difference between perfect and random list for deletion. What is the difference between deletion of 12 in the first implementation and deletion of 10 in the second? Thanks in advance

[yoandmario]

Would you mind providing an example of a geometric data structure that uses skip lists? I want to implement a skip list as my final project for my data structures class and I'm curious how I could implement it further. Great lecture!