Skip list
= Skip list
{wiki}
= Skiplist
{synonym}
A <skip list> stores an ordered <sequence> in a bottom <linked list>, with successively sparser <linked lists> above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update <time complexity> with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.