3 ms·

Looks like singlely linked lists in the linked article.

• thesz 4y ago
  Double linked lists would help navigate quicker. But let's discuss why even skip list on even single linked lists is not that easy. The problem with double-linked lists modified in parallel is that one should lock at least two places where changes are performed. When you lock two things, you need an order between them on which to lock first. Otherwise, it is possible to introduce deadlocks - first actor needs A and B and locks A, second actor needs A and B and locks B. Crucial part here is the need to lock more than one object. If I understand skip lists correctly, it is possible to insert element into several lists at once. Thus, the need to work on more than one element. Thus, the possibility of deadlock that needs to be accounted for.