3 ms·

Well, a skip list is just a bunch of linked lists...

• sesqu 17y ago
  I would describe it more as a multiply-linked list. The important distinction in a skip list is that you get random access, in a different sense of the term, and so binary search makes sense. Similarly, you could justify a binary (or another non-sequential) search on a traditional linked list by assuming huge evaluation costs.