4 ms·
> Skip lists are built upon double linked lists, I've always seen them with singly-linked lists; double doesn't give an average or worst-case order improvement
by dragonwriter 4y ago
> Skip lists are built upon double linked lists,
I've always seen them with singly-linked lists; double doesn't give an average or worst-case order improvement to anything, but it does make some ops faster within the same complexity class.
- thesz 4y agoOkay, skip lists are built upon singly-linked lists, but there are still need to lock more than one object to modify. The need to lock multiply objects at once is the potential source of deadlocks.